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

 

10026번: 적록색약

 

BFS, DFS 등을 이용해 2차원 맵을 탐색하는 그래프 탐색 문제다.
기본적이고 전형적인 유형에 아주 약간의 아이디어로 살짝 난이도를 올려놓아서 아주 까다롭지 않게 그래프 탐색 기본기를 익히기 좋은 문제라고 할 수 있다.

 

 

RGB로 표현한 2차원 맵을 탐색하는 문제다.

보통 주어진 2차원 맵을 탐색하는 문제에서 요구하는 목표는 길을 찾거나 맵 상 구분되는 영역의 크기를 구하거나 영역의 수를 세는 형태로 자주 등장한다.

 

 

여기에 추가적으로는 맵을 변화시키는 등의 요소를 더하는 것이 대부분이다.

이 문제도 색상 지도와 적록색약을 가져와 결국 맵에 변화 요소를 주고 변화 전, 후의 영역의 수를 구하도록 하는 문제다.

 

 

R과, G, B를 모두 구분하도록 그래프를 탐색시켜 적록색약이 아닌 사람이 봤을 때 구역의 수를 구하고 맵을 변경하거나 R과 G는 구분하지 않고 탐색하도록  적록색약인 사람이 봤을 때 구역의 수를 구해주면 된다.

 

 

---

 

 

문제의 포인트

그래프 탐색 문제에서 영역의 수 세기
그래프를 변화시키거나 조건을 변경해 탐색하기

 

 

그래프 탐색 문제에서 영역의 수 세기

 

이 문제는 우선 기본 맵이나 탐색 방법으로, 맵 상 구분되는 영역의 수를 세고 다시 한번 변경된 맵이나 방법을 통해 영역의 수를 세는 문제다.

즉, 우선 영역의 수를 세는 방법부터 알아야 한다.

 

 

먼저 기본적인 2차원 배열로 표현된 맵을 탐색시킬 때에는 특정 지점을 기준으로 상, 하, 좌, 우로 인접한 위치로 한칸 씩 이동시켜 나가듯 탐색해 나간다.

깊이 우선 탐색(DFS)으로 찾아갈지, 너비 우선 탐색(BFS)로 찾아갈지는 최단 경로를 찾는 경우를 제외하면 큰 의미 없는 선택인 경우가 대부분이다.

Stack을 쓰느냐 Queue를 쓰느냐 차이 외에는 구현상 차이날 부분도 없다.

 

 

0과 1로 이루어진 2차원 배열 맵에서 좌측 맨 윗줄을 시작점으로 1을 기준으로 탐색을 시킨다면 0을 만나기 전까지 상, 하, 좌, 우 인접한 모든 1을 탐색해 하나의 연속된 1로 채워진 영역을 탐색할 수 있다.

 

 

[0, 0] 부터 [N, N] 까지 방문하지 않았던 모든 위치를 대상으로 반복해서 탐색을 시키면 결국 연속되지 않은 모든 1의 영역을 찾을 수 있다.

 

 

만약 이렇게 맵 전체를 탐색해 나갈 때 연결되어있지 않은 새로운 영역을 발견하면 앞서 발견한 영역과 다른 새로운 영역으로 인식하고자 한다면 단순히 새로운 탐색을 시작할 때 카운터를 세어서 연속되지 않은 몇개의 영역이 존재하는지 파악할 수 있다.

필요에 따라서는 해당 영역을 다른 숫자로 채울 수도 있다.

 

 

백준 2667번 단지 번호 붙이기 문제가 이런 방법을 활용한 문제다.

본 적록색약 문제에서도 일단 이와 같은 방식으로 구분된 영역의 수를 세어야 한다.

여기에서는 숫자대신 R, G, B 3가지로 구분된 각각의 영역의 수를 세어주면 된다.

 

 

 

그래프를 변화시키거나 조건을 변경해 탐색하기

 

이것만으로는 문제가 요구하는 모든 구역의 수를 찾을 수 없다.

적록색약인 사람이 봤을 때 구역의 수를 구해줘야 한다.

 

 

이미 그래프를 탐색해 구분된 영역의 수를 세는 방법은 찾았으니 똑같은 방법으로 다시 탐색을 시키되 R과 G를 구분 없이 한가지 색으로 판단하도록 조건을 바꿔준다면 간단히 새로운 기준으로 영역 수를 다시 셀 수 있다.

 

 

가능한 또 다른 방법은 첫번째 탐색 시 맵 자체를 R을 G로 바꾸거나 G를 R로 바꿔버리는 방법이다.

이렇게 맵을 바꿔버리고 탐색만 다시 시킨다면 마찬가지로 간단하게 새로운 기준으로 영역 수를 셀 수 있다.

 

 

---

 

 

전체 Code

#include <iostream>
#include <queue>

using namespace std;

int N, normal_cnt, weak_cnt;

char map[100 + 10][100 + 10];
int visit[100 + 10][100 + 10];

queue<pair<int, int>> q;

void BFS(int r, int c, int visit_num) {
	int dr[] = {-1, 0, 1, 0};
	int dc[] = {0, 1, 0, -1};

	int curr_r, curr_c, next_r, next_c, i;
	char col;

	q.push(make_pair(r, c));
	visit[r][c] = visit_num + 1;
	col = map[r][c];
	if (map[r][c] == 'G')
		map[r][c] = 'R';

	while (!q.empty()) {
		curr_r = q.front().first;
		curr_c = q.front().second;
		q.pop();

		for (i = 0; i < 4; i++) {
			next_r = curr_r + dr[i];
			next_c = curr_c + dc[i];

			if (next_r < 0 || next_r >= N || next_c < 0 || next_c >= N) continue;
			if (map[next_r][next_c] != col) continue;
			if (visit[next_r][next_c] > visit_num) continue;

			q.push(make_pair(next_r, next_c));
			visit[next_r][next_c] = visit_num + 1;
			if (map[next_r][next_c] == 'G') {
				map[next_r][next_c] = 'R';
			}
		}
	}
}

int main() {
	cin.tie(0);
	cin.sync_with_stdio(0);

	int i, j;

	cin >> N;

	for (i = 0; i < N; i++) {
		cin >> map[i];
	}

	for (i = 0; i < N; i++) {
		for (j = 0; j < N; j++) {
			if (visit[i][j] == 0) {
				BFS(i, j, 0);
				normal_cnt++;
			}
		}
	}

	for (i = 0; i < N; i++) {
		for (j = 0; j < N; j++) {
			if (visit[i][j] == 1) {
				BFS(i, j, 1);
				weak_cnt++;
			}
		}
	}

	cout << normal_cnt << " " << weak_cnt << "\n";

	return 0;
}