(cpp) Baekjoon 10026번 문제 ‘적록색약’ - 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색
Baekjoon 10026번 문제 ‘적록색약’ - 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색
예제입력1에 대한 문제풀이
1. 시작점과 상하좌우로 인접한 지점들을 탐색하여 해당 지점과 같은 색깔이면 같은 그룹으로 분류되고, 그렇지 않으면 다른 그룹이 된다. 이떄, 색약이 있는 사람은 R과 G를 같은 그룹으로 본다.
2. 색약 없는 사람의 check박스와 색약 있는 사람의 check박스를 각각 만든다.
3. [1,1]을 시작큐에 넣었을 떄 탐색 후보군은 [1,2],[2,1]이 된다. check1[1][1]=1로 체크했을 때, [1,2]는 [1,1]과 같으므로 ‘check1[1][2]=check1[1][1]’이 되고, [2,1]은 [1,1]과 다르므로 ‘check1[2][1] = check1[1][1] + 1’ 이 된다. 반면, 색약이 있는 사람의 check2의 경우 ‘check2[1][2] = check2[2][1] = check[1][1]’ 이다.
4. check를 구성하는 가장 큰 수를 각각 출력한다.
틀린코드
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<queue>
using namespace std;
int n;
char g[200][200];
int check1[200][200], check2[200][200];
char state;
queue<pair<int, int>> q;
//상 하 좌 우
int r_pos[4] = {-1,1,0,0};
int c_pos[4] = {0,0,-1,1};
int result1, result2 = 0;
void solution() {
q.push(make_pair(1, 1));
check1[1][1] = 1;
check2[1][1] = 1;
while(!q.empty()) {
int cur_r = q.front().first;
int cur_c = q.front().second; //현재위치 1,1
cout << cur_r<<',' << cur_c <<'\n';
q.pop();
for (int i = 0; i < 4; i++) {
int next_r = cur_r + r_pos[i];
int next_c = cur_c + c_pos[i];
if (0 < next_r && next_r <= n && 0 < next_c && next_c <= n && check1[next_r][next_c]==0) {
if (g[next_r][next_c] == g[cur_r][cur_c]) {
check1[next_r][next_c] = check1[cur_r][cur_c];
check2[next_r][next_c] = check2[cur_r][cur_c];
}
else if (g[next_r][next_c] != g[cur_r][cur_c]) {
if (((g[next_r][next_c] == 'R' && g[cur_r][cur_c] == 'G') || (g[next_r][next_c] == 'G' && g[cur_r][cur_c] == 'R'))) {
check1[next_r][next_c] = check1[cur_r][cur_c] + 1;
check2[next_r][next_c] = check2[cur_r][cur_c];
}
else {
check1[next_r][next_c] = check1[cur_r][cur_c] + 1;
check2[next_r][next_c] = check2[cur_r][cur_c] + 1;
}
}
q.push(make_pair(next_r, next_c));
}
}
}
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> state;
g[i][j] =state;
check1[i][j] = 0;
check2[i][j] = 0;
}
}
solution();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (check1[i][j] >= result1) {
result1 = check1[i][j];
}
if (check2[i][j] >= result2) {
result2 = check2[i][j];
}
}
}
cout << result1 << ' ' << result2;
return 0;
}
- 반례 : 2 RGGR
맞은 코드
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<queue>
using namespace std;
int n;
char g[101][101];
int check[101][101];
char state;
//상 하 좌 우
int r_pos[4] = {-1,1,0,0};
int c_pos[4] = {0,0,-1,1};
void solution(int cur_r, int cur_c) {
if (check[cur_r][cur_c] == 1) return; //현재 위치를 방문한 적이 있다면 return
check[cur_r][cur_c] = 1; //방문한적 없다면 체크
for (int i = 0; i < 4; i++) {
int next_r = cur_r + r_pos[i]; //현재 위치의 상하좌우 탐색하여
int next_c = cur_c + c_pos[i];
if (check[next_r][next_c] == 0 && g[next_r][next_c] == g[cur_r][cur_c]) {
//현재 위치와 같은 값을 가진 곳이 있다면 그곳으로 이동
solution(next_r, next_c); //next_r,next_c가 새로운 시작점이 됨.
}
}
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> state;
g[i][j] = state;
check[i][j] = 0;
}
}
int cnt = 0;
//적록색약이 아닌 사람이 보았을 때의 구역의 수
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++)
{
if (check[i][j] == 0) {
solution(i, j);
cnt++;
}
}
}
cout << cnt << ' ';
cnt = 0;
//적록색약인 사람이 보았을 때 구역의 수
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
check[i][j] = 0;
if (g[i][j] == 'R') {
g[i][j] = 'G';
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++)
{
if (check[i][j] == 0) {
solution(i, j);
cnt++;
}
}
}
cout << cnt ;
return 0;
}
맞은 코드 풀이
처음에는 현재위치의 값과 다음 위치의 값이 같으면 같은 그룹이므로 같은 숫자로 체크를 하고, 다른 경우는 현재 그룹 숫자에 1을 더한 수로 체크하는 방식을 떠올렸다. 그러나 이렇게 하면
2
RG
GR
을 처리하지 못한다. [1,1]에서 시작하여 다음 후보군은 [2,1]과 [1,2]가 된다. 만약 [1,1]이 1번 그룹이라 하면 이 둘은 각각 2번 그룹이 된다. [2,1]이 새로운 시작점이 되면 [1,1]과 [2,2]가 후보군이 되는데 [1,1]은 방문한 적이 있으므로 갈수 없고 [2.2]는 3번 그룹이 된다. 문제는 여기서 발생하는데, 다음 시작점인 [1,2]는 현재 2번 그룹이고 후보군이 [1,1]과 [2,2]인데 이 둘 모두 방문할 수 없으므로 프로그램이 종료되어 버린다. 그렇다면 최대값은 check[2][2]에 입력되어 있는 3이 되기에 틀린 답이다.
이런 문제를 해결하기 위해 너비 우선 탐색 + 깊이 우선 탐색이 추가되어야 한다. 1번 그룹에 해당하는 것들을 모두 탐색하고, 2번 그룹에 해당하는 것들을 모두 탐색하는 식으로 이뤄진다. [1,1]에서 시작하여 인접한 곳들을 탐색했을 때 [1,1]과 그 값이 같으면 새로운 시작점으로 갱신해준다. 이때 방문한 곳들은 ‘True or False’로 체크한다. 1번 그룹에 속할 수 있는 모든 곳들을 방문 완료하면 함수가 끝난다. 함수가 한번 종료되면 cnt++된다. 그 다음으로 map을 모두 돌면서 아직 방문하지 않은 점이 있다면 그 지점을 새로운 시작점으로 하여 bfs함수에 다시 넣어준다. 그럼 새로운 시작점을 중심으로 위의 과정이 반복된다. 이렇게 해서, 모든 (i,j)를 한번씩 새로운 시작점에 넣어주어 bfs를 돌리는 과정을 거치다가 더이상 넣어줄 시작점이 없는 경우 함수의 실행 횟수를 출력한다.
적록색맹의 경우, 같은 함수를 그대로 사용하기 위해 input에서 ‘R’을 ‘G’로 바꿔주는 작업을 먼저 수행한 후 같은 함수를 적용한다.
- 좀더 단순하게 생각할 필요가 있다.
- 처음엔 체크박스를 두 개 만들거나, 함수를 두 개 만들거나 등의 생각을 했었는데 단순히 map을 한번 바꿔 주는 것이 더욱 편리하다.
- 단, 그 과정 중에 변수 초기화를 잊지 말아야 한다.
- bfs함수 구성에서, 시작큐를 계속해서 업데이트 시키는 방법 대신 재귀를 사용한다.