[백준] 10026 - 적록색약

www.acmicpc.net/problem/10026

10026번: 적록색약

 위 문제는 순수 BFS(너비우선 탐색)와 DFS(깊이우선탐색) 두가지 모두로 해결이 가능하다. 색약의 경우만 R, G중 하나를 R 혹은 G로 모두 변경 후에 다시 BFS, DFS를 돌리면 색상의 구역을 구분할 수 있다. 아래 코드는 BFS, DFS 모두를 구현한 정답이다. 직장내 SW 검정이 있어 멘토링을 하느라 두가지 방식 모두 구현하였다. 아래 코드에서 관심있게 볼 포인트는 BFS는 Queue, DFS는 Stack 혹은 재귀(Recursion)로 구현이 가능한데, Queue, Stack으로 각각 구현할 경우 동일 로직에서 Queue <--> Stack만 서로 바꿔주면 BFS, DFS 구현이 가능하다는 점이다.

#include <iostream>
using namespace std;
#include <queue>
#include <stack>
#include <stdio.h>
#include <string.h>

typedef struct _loc {
    int y;
    int x;
}loc;

int N;
char map[101][101];
bool visited[101][101];
int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, 1, 0, -1};
int result_1 = 0;
int result_2 = 0;

void bfs(int y, int x, char color){
    loc item;
    item.y = y;
    item.x = x;

    queue<loc> bfs_queue;
    visited[item.y][item.x] = true;
    bfs_queue.push(item);

    while(!bfs_queue.empty()){
        loc pop = bfs_queue.front();
        bfs_queue.pop();
        for(int i=0; i<4; ++i) {
            int ny = pop.y + dy[i];
            int nx = pop.x + dx[i];
            if(ny >= 1 && ny <= N && nx >= 1 && ny <= N && visited[ny][nx] == false && map[ny][nx] == color){
                loc temp;
                temp.y = ny;
                temp.x = nx;
                visited[temp.y][temp.x] = true;
                bfs_queue.push(temp);
            } 
        }
    }
}

void dfs(int y, int x, char color){
    loc item;
    item.y = y;
    item.x = x;

    stack<loc> dfs_stack;
    visited[item.y][item.x] = true;
    dfs_stack.push(item);

    while(!dfs_stack.empty()){
        loc pop = dfs_stack.top();
        dfs_stack.pop();
        for(int i=0; i<4; ++i) {
            int ny = pop.y + dy[i];
            int nx = pop.x + dx[i];
            if(ny >= 1 && ny <= N && nx >= 1 && ny <= N && visited[ny][nx] == false && map[ny][nx] == color){
                loc temp;
                temp.y = ny;
                temp.x = nx;
                visited[temp.y][temp.x] = true;
                dfs_stack.push(temp);
            } 
        }
    }
}


int main() {
    scanf("%d", &N);

    for(int i=1; i<=N; ++i) {
        char temp[101];
        scanf("%s", temp);
        for(int j=1; j<=N; ++j) {
            map[i][j] = temp[j-1];
        }
    }

    memset(visited, false, sizeof(visited));

    for(int i=1; i<=N; ++i) {
        for(int j=1; j<=N; ++j) {
            if(visited[i][j] == false){
                bfs(i, j, map[i][j]);
                result_2 += 1;
            }
        }
    }

    for(int i=1; i<=N; ++i) {
        for(int j=1; j<=N; ++j) {
            if(map[i][j] == 'G'){
                map[i][j] = 'R';
            }
        }
    }

    memset(visited, false, sizeof(visited));

    for(int i=1; i<=N; ++i) {
        for(int j=1; j<=N; ++j) {
            if(visited[i][j] == false){
                dfs(i, j, map[i][j]);
                result_1 += 1;
            }
        }
    }

    printf("%d %d\n", result_2, result_1);

    return 0;
}