[백준 BOJ][C++]10026번 적록색약 풀이: BFS/DFS

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

10026번: 적록색약

 

 

 이 문제는 BFS 알고리즘을 사용하여 해결할 수 있습니다. 

 

 먼저 init_visit() 함수와 all_visit() 함수는 각각 visit 배열을 0으로 초기화하는 함수와 모든 구역을 방문했는지를 체크하기 위한 함수입니다. 

 

 먼저 적록색약이 아닌 사람을 기준으로 탐색을 시작합니다. 

 

 모든 구역을 탐색해야지만 구역의 수를 알아낼 수 있겠죠? 그렇기 때문에 all_visit() 함수를 사용하여 모든 구역을 방문할 때까지 while문을 돌립니다. 

 

 이때 각 turn 마다 queue에 처음으로 push 될 구역의 위치는 아직 방문하지 않은 구역의 위치가 됩니다. 

 

 이 위치의 해당하는 색을 기준으로 bfs를 시작합니다. 

 

 bfs가 끝나면 구역의 수를 나타내는 변수 cnt를 증가시키고 모든 구역을 방문할 때까지 이 과정을 반복합니다. 

 

 모든 과정이 끝나고 나면 bfs() 함수는 총 구역의 수를 return 합니다. 

 

 

 적록색약인 사람을 기준으로 탐색하기 전에 중첩 for문을 통해 map 안의 'G' 문자를 모두 'R' 로 바꾸어 줍니다. 

 

 그러고 나서 init_visit() 함수로 모둔 구역의 방문 표시를 0으로 해준 뒤, 다시 bfs()를 호출하면 적록색약인 사람이 본 총 구역의 수를 얻을 수 있습니다. 

 

 

#include<iostream>
#include<queue>
#include<algorithm>

using namespace std;

typedef pair<int, int> pp;

int n;
char map[101][101];
int visit[101][101] = { 0, };

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

void init_visit() {

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

int all_visit() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (visit[i][j] == 0)
				return 0;
		}
	}
	return 1;
}

int bfs() {
	
	int cnt = 0;

	pp p;
	int tx, ty;

	tx = ty = 0;

	while (!all_visit()) { //모두 방문할 때까지
		queue<pp> q;

		q.push({ tx, ty });
		visit[ty][tx] = 1;
		char c = map[ty][tx];

		while (!q.empty()) { //문자 c에 대한 bfs
			p = q.front();
			q.pop();

			for (int i = 0; i < 4; i++) {
				tx = p.first + dx[i];
				ty = p.second + dy[i];

				if (tx < 0 || tx >= n || ty < 0 || ty >= n)
					continue;
				if (visit[ty][tx] == 1)
					continue;
				if (map[ty][tx] != c)
					continue;

				visit[ty][tx] = 1;
				q.push({ tx, ty });
			}
		}

		for (int i = 0; i < n; i++) { //아직 방문하지 않은 문자 위치
			for (int j = 0; j < n; j++) {
				if (visit[i][j] == 0) {
					tx = j;
					ty = i;
				}
			}
		}

		cnt++;
	}

	return cnt;
}

int main(void) {

	cin >> n;

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

	int a = bfs();  //적록색약이 아닌 사람이 본 개수 

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (map[i][j] == 'G') //G를 R로 변경
				map[i][j] = 'R';
		}
	}
    
	init_visit();
	int b = bfs();  //적록색약인 사람이 본 개수 

	cout << a << " " << b;

	return 0;
}