[백준] 적록색약 10026번 (c++)

출처 : 10026번: 적록색약 (acmicpc.net)

10026번: 적록색약

풀이 방법

적록색약이 아닌 경우는 일반적인 BFS 풀이하면 된다

하지만 적록색약인 경우는 R, G인 경우를 판단하여 불린 값에 넣어 두고 

따로 이런 경우를 빼내어서 R,G을 같은 색으로 취급해주었다.

BFS1이 적록색약이 아닌경우 함수 BFS2가 적록색약인 경우의 함수이다.

visited를 중간에 0으로 초기화해주어야 BFS1과 BFS2 가 섞이지 않는다

#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
int N;
int visited[101][101];
vector<string> board;
// 적록색약 x
void BFS1(int y, int x) {
    queue<pii> que;
    que.push(make_pair(y, x));
    char color = board[y][x];

    while (!que.empty()) {
        int y = que.front().first;
        int x = que.front().second;
        que.pop();
        for (int i = 0;i < 4;i++) {
            int nextX = x + dx[i];
            int nextY = y + dy[i];
            if (nextX >= 0 && nextX < N && nextY >= 0 && nextY < N) {
                if (board[nextY][nextX] == color) {
                    if (visited[nextY][nextX] == 0) {
                        visited[nextY][nextX] = 1;
                        que.push(make_pair(nextY, nextX));
                    }
                }

            }
        }
    }
    return;
}
//적록 색약 o
void BFS2(int y, int x) {
    queue<pii> que;
    que.push(make_pair(y, x));
    char color = board[y][x];
    bool red_green =false;
    // R,G 이면 red_green 을 true로 해준다
    if (color == 'R' || color == 'G') {
        red_green = true;
    }

    while (!que.empty()) {
        int y = que.front().first;
        int x = que.front().second;
        que.pop();
        for (int i = 0;i < 4;i++) {
            int nextX = x + dx[i];
            int nextY = y + dy[i];
            if (nextX >= 0 && nextX < N && nextY >= 0 && nextY < N) {
                // R,G인 경우
                if (red_green) {
                        if (board[nextY][nextX] == 'R' || board[nextY][nextX] == 'G') {
                            if (visited[nextY][nextX] == 0) {
                                visited[nextY][nextX] = 1;
                                que.push(make_pair(nextY, nextX));
                            }
                        }
                }
                //B인 경우
                else {
                    if (board[nextY][nextX] == color) {
                        if (visited[nextY][nextX] == 0) {
                            visited[nextY][nextX] = 1;
                            que.push(make_pair(nextY, nextX));
                        }
                    }
                }

            }
        }
    }
    return;
}

int main() {
    cin >> N;
    memset(visited, 0, sizeof(visited));
    for (int i = 0;i < N;i++) {
        string st;
        cin >> st;
        board.push_back(st);
    }
    int ans1 = 0, ans2 = 0;
    // 적록색약이 아닌 경우
    for (int i = 0;i < N;i++) {
        for (int j = 0;j < N;j++) {
            if (visited[i][j] == 0) {
                visited[i][j] = 1;
                ans1++;
                BFS1(i, j);
            }
        }
    }
    memset(visited, 0, sizeof(visited));
    // 적록색약인 경우
    for (int i = 0;i < N;i++) {
        for (int j = 0;j < N;j++) {
            if (visited[i][j] == 0) {
                visited[i][j] = 1;
                ans2++;
                BFS2(i, j);
            }
        }
    }
    cout << ans1 <<" " << ans2;
    return 0;
}