[백준 #10026 c++] 적록색약, DFS

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

10026번: 적록색약

 

문제 자체는 어렵지는 않다. DFS개념을 가지고 있다면 접근하는데는 큰 지장이 없다.

하지만 DFS에서 응용이 필요한데 이 부분에서 많이 헤맬 수 있다.

 

1차원적으로 생각해 2중배열에서의 DFS 코드를 짜고 제출해버리면 당연히 반례를 만나서 10%도 가지 못하고 틀렸다고 나온다.

 

다음 예시를 보자.

 

n = 5

R	R	R	B	B
G	G	B	B	B
B	B	B	R	R
B	B	R	R	R
R	R	R	R	R

 

문제에 제시된 예제이다.

 

제일 왼쪽 위 R부터 시작해서 차례대로 DFS를 반복할 때,

인접한 같은 색상으로 가거나

R->G 혹은 G->R 일때에만 재귀로 함수를 호출하여 탐색을 한다고 해보자.

그리고 R<->G 상황에서만 적녹색약이 아닌 사람이 보는 구역 수(이하 cnt_a)를 1 증가시켜준다고 해보자.

(적녹색약인 사람이 보는 구역 수는 cnt_b 라고 정의하자)

 

이때 좌 우 상 하 순으로 탐색할 때

R -> R -> R -> G -> G

이렇게 R -> G 가 한 번만 나오며 cnt_a 의 증가값 1과 동일하다.

그리고 각 DFS 종료마다 cnt_a와 cnt_b를 각 1 증가시켜주면 된다.

이것 외에도 비슷한 예제를 해봐도 cnt_a 의 증가값을 R <-> G 의 횟수로 지정해도 되는 결과가 나온다.

 

 

하지만 다음 예제를 볼까?

 

n  = 4

R	G	R	G
G	G	R	R
R	G	R	G
G	G	R	R

 

(1, 1)에 위치한 R부터 탐색할 때,

R -> G -> R -> G -> R -> R -> G -> G -> R -> ... -> R

순으로 정확히 ㄹ자 형태로 탐색한다.

이 과정에서 R <-> G 의 횟수를 세 보면 10개가 나온다.

하지만 실제 cnt_a는 총 6개가 나와야 정답인걸 직관적으로 알 수 있다.

 

즉 응용이 필요하다는 얘기이다.

 

여기서 큐를 가져와서 R <-> G 상황일 때 그 위치를 큐에 넣고 현재 DFS가 종료된 후 큐에 있는 위치에 대해 순차적으로 DFS를 반복한다는 아이디어를 떠올려 보자.

 

똑같이 탐색을 하면

R 에서 DFS 종료, 이후 R의 오른쪽과 아래에 있는 G가 큐에 등록된다.

먼저 오른쪽 G를 탐색한 다음 아래 G를 탐색할 때 아래 G는 오른쪽 G에 의해 이미 탐색이 되었기 때문에 생략한다.

즉, 단 두 번의 DFS를 거쳤는데 구역 두 개의 탐색을 완벽히 끝낸 것이다.

 

큐에 등록된 친구들을 탐색하는 경우에만 cnt_a를 증가시켜 주면 정답이 된다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
using namespace std;

queue<pair<int, int>> q;
char pic[101][101];
bool visit[101][101];
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
int ca = 0;
int cb = 0;

void dfs(int x, int y) {
	visit[y][x] = true;
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (!visit[ny][nx]) {
			if (pic[y][x] == pic[ny][nx]) {
				dfs(nx, ny);
			}
			else if (pic[y][x] == 'R' && pic[ny][nx] == 'G' ||
				pic[y][x] == 'G' && pic[ny][nx] == 'R') {
				q.push({ nx, ny });
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n;
	cin >> n;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> pic[i][j];
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (!visit[i][j]) {
				dfs(j, i);
				while (!q.empty()) {
					auto pair = q.front(); q.pop();
					if (visit[pair.second][pair.first]) continue;
					dfs(pair.first, pair.second);
					ca++;
				}
				ca++;
				cb++;
			}
		}
	}

	cout << ca << ' ' << cb;
}

 

dfs 함수 부분에서 nx와 ny를 visit에서 확인할 때 nx와 ny의 범위를 지정해주어야 하지만 이상하게도 통과가 되었다.