[c++/백준] 10026번: 적록색약

문제 링크

10026번: 적록색약

풀이

DFS를 이용하는 문제

1. 먼저 방문하지 않은 곳부터 시작해서 모든 칸을 방문할 때까지 반복한다. 방문만 체크하고, 구역의 수는 answer1과 answer2에 갱신해준다.
2. 재귀는 한 칸에서 네 방향으로 방문하면서 현재의 칸과 색이 같을 때만 재귀호출해준다. 이 때 방문도 같이 체크한다.
   2-1. 적록색약인 경우는 flag 처리를 해줘서 v[y][x]와 v[ny][nx]가 R이거나 G인 경우 2번과 같이 처리한다.
3. 이렇게 한번의 DFS 함수 호출이 끝나면 해당 구역의 방문처리는 끝난 것이므로 answer 갱신을 해주고, 다음 구역(방문하지 않은)부터 DFS 함수를 호출해준다.

코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int n;
vector<vector<char>> v;

int dy[4] = { -1,0,1,0 };
int dx[4] = { 0,1,0,-1 };

vector<vector<int>> visit;

void DFS(bool flag, int y, int x)
{
	for (int i = 0; i < 4; i++)
	{
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (ny < 0 || ny >= n || nx < 0 || nx >= n) continue;
		if (visit[ny][nx] == 1) continue;

		if (v[y][x] == v[ny][nx])
		{
			visit[ny][nx] = 1;
			DFS(flag, ny, nx);
		}
		else if (flag == true)
		{
			if ((v[y][x] == 'R' && v[ny][nx] == 'G') ||
				(v[y][x] == 'G' && v[ny][nx] == 'R'))
			{
				visit[ny][nx] = 1;
				DFS(flag, ny, nx);
			}
		}
	}
}

int main(void)
{
	cin >> n;
	
	v.resize(n, vector<char>(n));
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cin >> v[i][j];
		}
	}

	visit.resize(n, vector<int>(n));

	int answer1 = 0;
	int answer2 = 0;

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (visit[i][j] == 0)
			{
				answer1++;
				DFS(false, i, j);
			}
		}
	}

	visit.clear();
	visit.resize(n, vector<int>(n));
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (visit[i][j] == 0)
			{
				answer2++;
				DFS(true, i, j);
			}
		}
	}

	cout << answer1 << " " << answer2 << endl;

	return 0;
}