10026 적록색약

문제를 읽고난 후, '탐색' 을 가장먼저 생각했다면 올바르게 접근한 것이다.

이 문제는 DFS 또는 BFS 로 접근가능하고 필자의 경우 BFS 로 풀이해보았다.

'기본 알고리즘' 카테고리에 추가로 DFS와 BFS 의 대략적인 개념을 올려두었다.

접근은 우선 

 1) 적록색약이 아닌 사람은 R,G,B 각각의 부분에 대해 count 할 것.

 2) 적록색약의 경우 R와 G 중 R을 G로 바꾸어 부분을 구하거나, 또는 G를 R로 바꾸어 계산한다.

라는 기본적인 구현에 대한 생각을 염두에 두어야 한다.

BFS와 DFS에 관한 기본 개념을 알고 있을 것이라 가정하고, 소스코드를 아래 첨부해 두었다.

최적화된 것은 아니기에, 더 짧거나 혹은 더 메모리를 적게 소모하는 코드에 대해서는 백준 10026문제 맞은사람을 확인해보길 바란다.

<소스코드>

#include <cstdio>
#include <queue>
#include <utility>
using namespace std;

int N,cnt,dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};

char mat[101][101];

bool visit[101][101];

queue<pair<int,int>> q;

void BFS(int x,int y){

    q.push(make_pair(x,y));

    while(!q.empty()){

        int temp_x = q.front().first, temp_y = q.front().second;
        visit[temp_x][temp_y] = true; q.pop();

        for(int i = 0; i < 4; i++){

            int nx = temp_x+dir[i][0], ny = temp_y+dir[i][1];
            if(nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
            if(!visit[nx][ny] && mat[nx][ny]==mat[x][y]){

                visit[nx][ny] = true;
                q.push(make_pair(nx,ny));

            }
        }
    }
    cnt++;
}

void init(){
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++) if(!visit[i][j]) BFS(i,j);
    }
}

int main(){

    scanf("%d",&N);
    for(int i = 0; i < N; i++) scanf("%s",mat[i]);
    init();

    printf("%d ",cnt);
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++) visit[i][j] = false;
    }
    cnt = 0;

    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            if(mat[i][j] == 'G') mat[i][j] = 'R';
        }
    }
    init();
    printf("%d\n",cnt);
    return 0;

}