10026번 적녹색약

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

풀이

이 문제는 적록색약인 사람과 그렇지 않은 사람이 보는 그림에서 각각의 구역의 수를 세는 문제입니다. BFS (Breadth-First Search)를 사용하여 연결된 구성 요소의 수를 계산하는 방식으로 해결할 수 있습니다.

1. 두 가지 보드 준비:
   • 일반적인 경우를 위한 board: ‘R’, ‘G’, ‘B’를 각각 다른 숫자로 매핑합니다. (예: R=1, G=2, B=3)
   • 적록색약인 경우를 위한 board_week: ‘R’과 ‘G’를 같은 숫자로 매핑하고 ‘B’는 다른 숫자로 매핑합니다. (예: R=1, G=1, B=3)
2. BFS 함수 구현:
   • BFS(board, visited, x, y) 함수는 주어진 (x, y) 좌표에서 시작하여 동일한 색상을 가진 모든 인접한 셀을 탐색합니다.
   • visited 배열을 사용하여 이미 방문한 셀을 추적하여 중복 계산을 방지합니다.
   • 큐를 사용하여 BFS 탐색을 수행하고, 현재 셀의 색상과 동일한 인접 셀을 큐에 추가하고 방문 처리합니다.
3. 구역 수 계산:
   • 두 개의 별도의 visited 배열(visited 및 visited_week)을 사용하여 일반적인 경우와 적록색약인 경우를 각각 추적합니다.
   • 두 개의 카운터(cnt 및 cnt_week)를 0으로 초기화합니다.
   • 전체 보드를 순회하면서:
     • 만약 현재 셀이 일반 visited 배열에서 방문되지 않았다면, BFS(board, visited, i, j)를 호출하고 cnt를 1 증가시킵니다.
     • 만약 현재 셀이 적록색약 visited_week 배열에서 방문되지 않았다면, BFS(board_week, visited_week, i, j)를 호출하고 cnt_week를 1 증가시킵니다.
4. 결과 출력:
   • 최종적으로 cnt와 cnt_week를 출력합니다.

이 방법은 두 가지 다른 관점에서 그림의 연결된 구성 요소를 효율적으로 계산하여 문제를 해결합니다.

시간 복잡도: 이 문제는 $N \times N$ 크기의 그리드에서 BFS를 두 번 수행합니다. BFS는 모든 정점과 간선을 한 번씩 방문하므로, 시간 복잡도는 $O(V + E)$입니다. 여기서 $V$는 그리드의 칸 수 ($N^2$), $E$는 간선의 수 (각 칸마다 최대 4개의 인접한 칸으로 연결될 수 있으므로 대략 $4N^2$)입니다. 따라서, 두 번의 BFS를 포함한 전체 시간 복잡도는 $O(N^2)$입니다.

공간 복잡도: 큐에 최악의 경우 $O(N^2)$개의 칸이 저장될 수 있으며, visited 배열 또한 $O(N^2)$의 공간을 사용합니다. 따라서, 공간 복잡도는 $O(N^2)$입니다.

코드

10026.cpp

#include <bits/stdc++.h>
using namespace std;
constexpr array<int, 4> dx = {1, 0, -1, 0};
constexpr array<int, 4> dy = {0, 1, 0, -1};
void BFS(const vector<vector<int>>& board, vector<vector<bool>>& visited, int x, int y){
    queue<pair<int, int>> q;
    q.push({x, y});
    visited[x][y] = true;
    const int currColor = board[x][y];
    while(!q.empty()){
        auto [x, y] = q.front();
        q.pop();
        for(int i = 0;i<4;i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx < 0 || nx >= board.size() || ny < 0 || ny >= board[0].size() || visited[nx][ny] || board[nx][ny] != currColor){
                continue;
            }
            visited[nx][ny] = true;
            q.push({nx, ny});
        }
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    cin >> N;
    auto board = vector(N, vector(N, 0)); // 0: Unknown, 1: Red, 2: Green, 3: Blue
    auto board_week = vector(N, vector(N, 0));
    string s;
    for(int i = 0;i<N;i++){
        cin >> s;
        for(int j = 0;j<N;j++){
            if(s[j] == 'R'){
                board[i][j] = 1;
                board_week[i][j] = 1;
            }
            else if(s[j] == 'G'){
                board[i][j] = 2;
                board_week[i][j] = 1;
            }
            else if(s[j] == 'B'){
                board[i][j] = 3;
                board_week[i][j] = 3;
            }
        }
    }
    int cnt = 0, cnt_week = 0;
    auto visited = vector(N, vector(N, false));
    auto visited_week = vector(N, vector(N, false));
    for(int i = 0;i<N;i++){
        for(int j = 0;j<N;j++){
            if(!visited[i][j]){
                BFS(board, visited, i, j);
                cnt++;
            }
            if(!visited_week[i][j]){
                BFS(board_week, visited_week, i, j);
                cnt_week++;
            }
        }
    }
    cout << cnt << " " << cnt_week << '\n';
    return 0;
}

Standard Input (stdin): 5 RRRBB GGBBB BBBRR BBRRR RRRRR

⏳ Running... C++