백준 10026 - 적록색맹 - DFS

문제

문제링크 : https://www.acmicpc.net/problem/10026

풀이전략

1. 기존에 같은 값들만 찾는 DFS를 한개, 적록색맹일때의 값을 찾는 DFS를 한개 만들어 구별하여 해결한다.
2. 체크배열을 따로 만들어 기존에 주어진 input에 값을 바꾸지 않도록 한다.

코드

#include<bits/stdc++.h>

using namespace std;

int N;
char a[102][102];
//체크배열
bool ch[102][102];
// 가로세로 이동을 위한 배열
int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, 1, 0, -1};
int normalCnt = 0, oddCnt = 0;
// 일반적인 사람의 DFS
void nomalPeople(int r, int c, char color){

    for(int i=0; i<4; i++){
        int rr = r+dy[i];
        int cc = c+dx[i];
        if(a[rr][cc] == color && ch[rr][cc] == false){
            ch[rr][cc] = true;
            nomalPeople(rr, cc, color);
        }
    }
}
//  적록색맹의 DFS
void oddPeople(int r, int c, char color){
    if(color == 'B'){
            for(int i=0; i<4; i++){
                int rr = r+dy[i];
                int cc = c+dx[i];
                if(a[rr][cc] == color && ch[rr][cc] == false){
                    ch[rr][cc] = true;
                    oddPeople(rr, cc, color);
            }
        }
    }
    else{
        for(int i=0; i<4; i++){
                int rr = r+dy[i];
                int cc = c+dx[i];
                if((a[rr][cc] == 'R' || a[rr][cc] == 'G') && ch[rr][cc] == false){
                    ch[rr][cc] = true;
                    oddPeople(rr, cc, color);
                }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    // freopen("../input.txt","rt",stdin);
    cin >> N;
    // 이미 처리한 문자는 #으로 바꾸기
    

    for(int i=1; i<=N; i++){
        for(int j=1; j<=N; j++){
            cin >> a[i][j];
        }
    }
    memset(ch, false, sizeof(ch));
    for(int i=1; i<=N; i++){
        for(int j=1; j<=N; j++){
            if(ch[i][j] == false){
                ch[i][j] = true;
                nomalPeople(i, j, a[i][j]);
                normalCnt++;
            }
        }
    }
    memset(ch, false, sizeof(ch));
    for(int i=1; i<=N; i++){
        for(int j=1; j<=N; j++){
            if(ch[i][j] == false){
                ch[i][j] = true;
                oddPeople(i, j, a[i][j]);
                oddCnt++;
            }
        }
    }
    cout << normalCnt << " " << oddCnt << '\n';
    return 0;
}

소감

적록색맹의 경우 parameter에 color를 주어 B일때 그리고 B가 아닐때 두가지 경우에 맞추어 코드를 만들었다. 다른분들은 BFS로 한번에 처리하셨다... 나도 BFS도 공부해야겠다.