[백준/C++] 10026 적록색약

https://www.acmicpc.net/problem/10026

10026번: 적록색약

코드

#include <iostream>
using namespace std;

int n, division = 0, nodivision = 0;
int dx[4] = { 0, 0, 1,-1 }, dy[4] = { 1,-1,0,0 };
bool dv[101][101], ndv[101][101];
string arr[101];

void d_dfs(int x, int y) {
	dv[x][y] = true;
	for (int i = 0; i < 4; i++) {
		int gx = x + dx[i];
		int gy = y + dy[i];

		if (gx >= 0 && gx < n && gy >= 0 && gy < n && !dv[gx][gy])
			if (arr[gx][gy] == arr[x][y]) d_dfs(gx, gy);
	}
}

void nd_dfs(int x, int y) {
	ndv[x][y] = true;
	for (int i = 0; i < 4; i++) {
		int gx = x + dx[i];
		int gy = y + dy[i];

		if (gx >= 0 && gx < n && gy >= 0 && gy < n && !ndv[gx][gy])
		{
			if ((arr[x][y] != 'B' && arr[gx][gy] != 'B') || arr[x][y] == arr[gx][gy] && arr[gx][y] == 'B')
				nd_dfs(gx, gy);
		}
	}
}

int main()
{
	cin >> n;
	for (int i = 0; i < n; i++) cin >> arr[i];

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (!dv[i][j])
			{
				d_dfs(i, j);
				division++;
			}
			if (!ndv[i][j])
			{
				nd_dfs(i, j);
				nodivision++;
			}
		}
	}
	cout << division << " " << nodivision;
	return 0;
}

설명

전역변수 int로 n, 적록색약인 경우에 보는 구역의 수 nodivision, 적록색약이 아닌 경우에 보는 구역의 수 division, 탐색 위치 이동을 위해 방향을 뜻하는 배열 dx, dy를 선언한다. 그림정보를 저장할 string형 배열 arr와 각각의 경우에 배열 방문 여부를 저장할 dv, ndv를 bool 타입으로 선언한다. 
 

main 함수

n을 입력받고 그림정보를 반복문을 이용해서 입력받는다. 이중 for문으로 배열의 원소에 접근해 적록색약이 아니며 해당 배열 원소에 접근한 적이 없을 경우 d_dfs, 적록색약이며 해당 배열 원소에 접근한 적이 없을 경우 nd_dfs를 진행하고 각각 division, nodivision을 1씩 증가시킨다. 반복문 이후 division과 nodivision을 공백으로 구분해 출력한다.
 

dfs 함수

d_dfs, nd_dfs 모두 큰 틀은 유사하다. 현재 위치에 대해서 방문 여부를 true로 바꿔주고 반복문으로 이동할 4방향 모두 검사하는데 배열의 범위 내 속하며 이동할 곳이 미방문이라면 내부 if문을 수행한다. d_dfs, nd_dfs는 이 내부 if문이 서로 다르다. d_dfs는 적록색약이 아닌 경우, 즉 빨간색과 초록색을 다르게 보기 때문에 dfs를 수행하기 위해서는 현재 위치의 색과 이동할 위치의 색이 같아야 한다. nd_dfs는  현재 위치의 색과 이동할 위치의 색이 파란색으로 동일한 경우,  현재 위치의 색과 이동할 위치의 색이 모두 파란색이 아닌 경우에 dfs를 진행하면 된다. 
 

느낀 점

dfs를 적록색약이 아닌 경우, 적록색약인 경우에 대해 각각 돌려주면 되는 문제다. 오랜만에 dfs를 써서 처음에 조건 작성 시 약간 실수하긴 했으나 고친 뒤로는 문제없이 풀었다. 개인적으로 d_dfs, nd_dfs가 전체적으로 많이 유사하기 때문에 하나의 dfs에서 내부 분기를 할까 고민했는데 엄연히 다른 경우라고 생각해서 그냥 각각 구현했다.