[C언어] 백준 10026 적록색약

문제

적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다.

크기가 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번: 적록색약

 

문제 풀기 전 로직 생각하기

---

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 함수를 이용해 체크해 주는 방식으로 풀었습니다.