06. DFS/BFS 문제 [BOJ 10026번]

1. 관련 문제 🎯

문제 : 백준 10026 적록색약 🍎
난이도 : 골드 5

2. 문제 소개 🧩

1️⃣ 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다.

• 적록색약인 사람이 봤을 때, 빨간색과 초록색을 같은 색(빨간색 = 초록색)으로 본다.

2️⃣ N x N인 그리드의 각 칸은 R(빨강), G(초록), B(파랑) 중 하나로 색칠되어 있다.
3️⃣ 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다.
4️⃣ 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다.

• 위의 예시처럼, 적록 색약이 아닌 사람은 R(빨강)의 구역을 2개, G(초록)의 구역을 1개, B(파랑)의 구역을 1개로 총 4개의 구역을 본다.
• 그러나, 적록 색약인 사람은 R과 G가 같은 색으로 인식하기 때문에 R(빨강)의 구역을 2개, B(파랑)의 구역을 1개로 총 3개의 구역을 본다.

3. 문제 풀이 🖌️

이 문제의 핵심은 같은 색상이 상하좌우로 인접해 있는 경우, 같은 구역에 속한다는 것이다!

• 상하좌우를 살펴보면서 자신의 색상과 동일하다면, 해당 색상을 방문하고 이를 dfs로 탐색한다.

3-1. N x N의 칸으로 구성된 그림의 색상을 입력받는다.

• 이때, 적록색약이 보는 그림(arrGB의 배열)의 색상의 경우 R과 G일때, 같은 색상으로 인식하므로 같은 색상으로 입력받는다.

for(int i=0; i<N; i++){
        cin>>a;
        for(int j=0; j<N; j++){
            if(a[j]=='R'){
                arrRGB[i][j] = 1;   
                arrGB[i][j] = 1;
            }
            else if(a[j]=='B'){
                arrRGB[i][j] = 2;
                arrGB[i][j] = 2;
            }
            else {
                arrRGB[i][j] = 3;
                arrGB[i][j] = 1;
            }
        }
    }

3-2. dfs를 사용하여 같은 구역을 찾는다.

• 방문한 색상의 경우, arrRGB[x][y] = 0으로 변경한다.
• 상하좌우 중에서 자신과 같은 색상인 경우 탐색한다.
• 이때, 아래의 사진처럼 맨 처음의 R의 경우 '좌', '상'에 색상이 없기 때문에 이처럼 그림의 테두리를 유의하여 탐색한다.

void dfs(int x, int y, int color){
    arrRGB[x][y] = 0;	//방문한 경우

    if(y-1 >= 0 and arrRGB[x][y-1] == color)    dfs(x, y-1, color);    //상
    if(y+1 < N and arrRGB[x][y+1] == color)     dfs(x, y+1, color);	//하
    if(x+1 < N and arrRGB[x+1][y] == color)     dfs(x+1, y, color);    //우
    if(x-1 >= 0 and arrRGB[x-1][y] == color)    dfs(x-1, y,color);	//좌
}

3-3. 방문하지 않은 그림 색상의 칸의 경우, dfs로 방문해준다.

• 이때, arrRGB[i][j] != 0으로 방문하지 않은 지 확인한다.
• 그리고 방문하지 않은 곳의 경우 이전에 구역과 다른 구역이므로 구역의 개수를 늘려준다.

for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            if(arrRGB[i][j] != 0) {
                dfs(i,j,arrRGB[i][j]);
                areaRGB +=1;
            }
            if(arrGB[i][j] != 0){
                dfs2(i,j,arrGB[i][j]);
                areaRG += 1;
            }
        }
    }

4. 전체 코드 🔑

#include <iostream>
using namespace std;

int N = 0;
int arrRGB[100][100]; //빨간색이 있는 구역 = 1, 파랜색이 있는 구역 = 2, 초록색이 있는 구역 = 3
int arrGB[100][100];
int areaRGB = 0;    //적록색약이 아닌 사람이 보는 구역의 수
int areaRG = 0; //적록색약인 사람이 보는 구역의 수

void dfs(int x, int y, int color){
    arrRGB[x][y] = 0;

    if(y-1 >= 0 and arrRGB[x][y-1] == color)    dfs(x, y-1, color);    
    if(y+1 < N and arrRGB[x][y+1] == color)     dfs(x, y+1, color);
    if(x+1 < N and arrRGB[x+1][y] == color)     dfs(x+1, y, color);    
    if(x-1 >= 0 and arrRGB[x-1][y] == color)    dfs(x-1, y,color);
}

void dfs2(int x, int y, int color){
    arrGB[x][y] = 0;

    if(y-1 >= 0 and arrGB[x][y-1] == color)    dfs2(x, y-1, color);    
    if(y+1 < N and arrGB[x][y+1] == color)     dfs2(x, y+1, color);
    if(x+1 < N and arrGB[x+1][y] == color)     dfs2(x+1, y, color);    
    if(x-1 >= 0 and arrGB[x-1][y] == color)    dfs2(x-1, y,color);
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin>>N;
    string a;

    for(int i=0; i<N; i++){
        cin>>a;
        for(int j=0; j<N; j++){
            if(a[j]=='R'){
                arrRGB[i][j] = 1;   
                arrGB[i][j] = 1;
            }
            else if(a[j]=='B'){
                arrRGB[i][j] = 2;
                arrGB[i][j] = 2;
            }
            else {
                arrRGB[i][j] = 3;
                arrGB[i][j] = 1;
            }
        }
    }

    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            if(arrRGB[i][j] != 0) {
                dfs(i,j,arrRGB[i][j]);
                areaRGB +=1;
            }
            if(arrGB[i][j] != 0){
                dfs2(i,j,arrGB[i][j]);
                areaRG += 1;
            }
        }
    }

    cout<<areaRGB<<" "<<areaRG;
}

5. 결과 🏆