문제
적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다.
크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다)
예를 들어, 그림이 아래와 같은 경우에
RRRBB
GGBBB
BBBRR
BBRRR
RRRRR
적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 하지만, 적록색약인 사람은 구역을 3개 볼 수 있다. (빨강-초록 2, 파랑 1)
그림이 입력으로 주어졌을 때, 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100)
둘째 줄부터 N개 줄에는 그림이 주어진다.
출력
적록색약이 아닌 사람이 봤을 때의 구역의 개수와 적록색약인 사람이 봤을 때의 구역의 수를 공백으로 구분해 출력한다.
예제 입력 1
5
RRRBB
GGBBB
BBBRR
BBRRR
RRRRR
예제 출력 1
4 3
https://www.acmicpc.net/problem/10026
10026번: 적록색약
적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록)
www.acmicpc.net
문제 풀기 전 로직 생각하기
R, G, B 로 구성된 문자열들이 입력으로 들어오고 각각의 알파벳 끼리 상하좌우로
연결되어 알파벳 뭉텅이들의 갯수를 구하는 문제입니다.
한 가지 추가된 점은 두 번째 출력 부분에선 R과 G는 서로 같은 색으로 구분되어 갯수를 좀더 다르게 구하는 것인데요.
이 부분은 그냥 dfs를 한번 더 돌리면 될것 같습니다.
dfs에서 맨 처음 함수에 들어왔던 문자와 상하좌우 문자를 비교하면 될것 같습니다.
전체 코드
#include <stdio.h>
#include <string.h>
char str[101][101];
int n, r = 0, b = 0, g = 0, visited[101][101] = {};
void dfs(int y, int x, char *set)
{ // strchr로 현 위치의 문자가 set에 포함 되는지 확인
if (0 <= y && y < n && 0 <= x && x < n && !visited[y][x] && strchr(set, str[y][x]))
{
visited[y][x]++;
dfs(y + 1, x, set);
dfs(y - 1, x, set);
dfs(y, x + 1, set);
dfs(y, x - 1, set);
}
}
int main()
{
int ret = 0;
scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("\n%s", str[i]);
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (!visited[i][j])
{
if (str[i][j] == 'R' && ++r)
dfs(i, j, "R");
else if (str[i][j] == 'G' && ++g)
dfs(i, j, "G");
else if (str[i][j] == 'B' && ++b)
dfs(i, j, "B");
}
}
}
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
visited[i][j] = 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (!visited[i][j] && ++ret)
{
if (str[i][j] == 'B')
dfs(i, j, "B");
else
dfs(i, j, "RG");
}
}
}
printf("%d %d\n", r + g + b, ret);
return (0);
}
문제 해설
dfs를 두번 수행하는 데요
첫 번째 dfs에서는 각각의 인덱스를 R, G, B로 구분 하면서 체크해 방문하지 않은 곳이 있다면 각각의 변수값을 카운트 해주면서 dfs를 돌려 줍니다.
두 번째 dfs에서는 B인 경우 그냥 dfs 돌려 주고 그게 아닌 경우 RG를 인자값으로 보내 체크해 줍니다.
현재 위치의 문자와 인자값으로 보낸 set을 strchr 함수를 이용해 체크해 주는 방식으로 풀었습니다.
'백준 C언어' 카테고리의 다른 글
[C언어] 백준 13460 구슬 탈출 2 (2) | 2023.04.19 |
---|---|
[C언어] 백준 1987 알파벳 (0) | 2023.04.13 |
[C언어] 백준 2146 다리 만들기 (0) | 2023.04.11 |
[C언어] 백준 2206벽 부수고 이동하기 (0) | 2023.04.09 |
[C언어] 백준 1697 숨바꼭질 (0) | 2023.04.07 |