[백준 10026번] 적록색약

풀이

---

구역을 나누는 BFS,DFS의 일반적인 문제이지만 적록색약일 때의 구역도 나누어서 계산해야되는 문제이다.

구역을 나누는 문제처럼 풀되 적록색약을 위한 배열을 새로 만들어주어야한다.

소스코드

---

#include <iostream>
using namespace std;
 
int n;
char board[102][102], handi_board[102][102];
int result_board[102][102] = { 0, }, handi_result_board[102][102] = { 0, };
int que_x[1000001], que_y[1000001], head_x,tail_x, head_y,tail_y;
int cnt=1, handi_cnt = 1;
 
void push(int x, int y) {
    que_x[tail_x++] = x;
    que_y[tail_y++] = y;
}
 
int pop_x() {
    return que_x[head_x++];
}
 
int pop_y() {
    return que_y[head_y++];
}
 
void bfs(char word) {
    while (head_x != tail_x) {
        int x = pop_x();
        int y = pop_y();
 
        if (x + 1 <= n - 1 && board[x + 1][y] == word && result_board[x+1][y]==0) {
            push(x + 1, y);
            board[x+1][y] = 'n';
            result_board[x+1][y] = cnt;
        }
        if (x - 1 >= 0 && board[x - 1][y] == word&& result_board[x - 1][y] == 0) {
            push(x - 1, y);
            board[x-1][y] = 'n';
            result_board[x-1][y] = cnt;
        }
        if (y + 1 <= n - 1 && board[x][y + 1] == word&& result_board[x][y+1] == 0) {
            push(x, y+1);
            board[x][y+1] = 'n';
            result_board[x][y+1] = cnt;
        }
        if (y - 1 >= 0 && board[x][y - 1] == word&& result_board[x][y-1] == 0) {
            push(x, y-1);
            board[x][y-1] = 'n';
            result_board[x][y-1] = cnt;
        }
    }
}
 
void handi_bfs(char word) {
    while (head_x != tail_x) {
        int x = pop_x();
        int y = pop_y();
 
        if (x + 1 <= n - 1 && handi_board[x + 1][y] == word && handi_result_board[x + 1][y] == 0) {
            push(x + 1, y);
            handi_board[x+1][y] = 'n';
            handi_result_board[x + 1][y] = handi_cnt;
        }
        if (x - 1 >= 0 && handi_board[x - 1][y] == word&& handi_result_board[x - 1][y] == 0) {
            push(x - 1, y);
            handi_board[x-1][y] = 'n';
            handi_result_board[x - 1][y] = handi_cnt;
        }
        if (y + 1 <= n - 1 && handi_board[x][y + 1] == word&& handi_result_board[x][y + 1] == 0) {
            push(x, y + 1);
            handi_board[x][y+1] = 'n';
            handi_result_board[x][y + 1] = handi_cnt;
        }
        if (y - 1 >= 0 && handi_board[x][y - 1] == word&& handi_result_board[x][y - 1] == 0) {
            push(x, y - 1);
            handi_board[x][y-1] = 'n';
            handi_result_board[x][y - 1] = handi_cnt;
        }
    }
}
 
void debugging() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << result_board[i][j] << " ";
        }
        cout << '\n';
    }
}
 
void handi_debugging() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << handi_result_board[i][j] << " ";
        }
        cout << '\n';
    }
}
 
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> board[i][j];
            if (board[i][j] == 'R')
                handi_board[i][j] = 'G';
            else
                handi_board[i][j] = board[i][j];
        }
    }
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (board[i][j] == 'R' || board[i][j] == 'G' || board[i][j] == 'B') {
                head_x = 0;
                tail_x = 0;
                head_y = 0;
                tail_y = 0;
                push(i, j);
                bfs(board[i][j]);
                cnt++;
            }
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (handi_board[i][j] == 'G' || handi_board[i][j] == 'B') {
                head_x = 0;
                tail_x = 0;
                head_y = 0;
                tail_y = 0;
                push(i, j);
                handi_bfs(handi_board[i][j]);
                handi_cnt++;
            }
        }
    }
 
    cout << cnt - 1 << ' ' << handi_cnt - 1;
    return 0;
}