greentea31's Note

https://www.acmicpc.net/problem/10026

풀이 과정

격자 칸의 그림에 같은 색으로 이루어진 구역의 수를 구하되, 적록색약인 (적색과 녹색 구분 불가)사람과 적록색약이 아닌 사람이 보는 구역의 수를 각각 구하라는 문제이다.

BFS로 연결 요소의 수를 한 번 구하고, 모든 녹색을 적색으로 혹은 모든 적색을 녹색으로 바꿔서 색깔을 구분 못하게 한 뒤, BFS로 연결 요소의 수를 한 번 더 구해주면 된다.

소스 코드

#include <iostream>
#include <queue>
using namespace std;
char board[101][101];
bool visit[101][101];
int dy[4] = {0, 1, 0, -1};
int dx[4] = {1, 0, -1, 0};
int N;

void bfs(int y, int x) {
    queue<pair<int, int>> Q;
    visit[y][x] = true;
    Q.push(make_pair(y, x));

    while(!Q.empty()) {
        auto cur = Q.front(); Q.pop();
        for (int i = 0; i < 4; i++) {
            int ny = cur.first + dy[i];
            int nx = cur.second + dx[i];
            
            if (0 <= ny && ny < N && 0 <= nx && nx < N) {
                if (board[ny][nx] != board[y][x]) continue;
                if (visit[ny][nx]) continue;
                visit[ny][nx] = true;
                Q.push(make_pair(ny, nx));
            }
        }
    }

}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N;
    int answer = 0;
    int answer2 = 0;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> board[i][j];
        }
    }

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (visit[i][j]) continue;
            bfs(i, j);
            answer++;
        }
    }

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            visit[i][j] = false;
            if (board[i][j] == 'G') board[i][j] = 'R';
        }
    }

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (visit[i][j]) continue;
            bfs(i, j);
            answer2++;
        }
    }

    cout << answer << ' ' << answer2;

    return 0;
}