문제 설명

• 그림에 같은 색으로 연결된 부분을 하나의 구역으로 봤을 때, 그 구역의 개수를 구하는 문제
• 이 때, 정상인은 rgb를 다 따로 구분할 수 있지만, 적록색약인 사람은 r과 g를 구분하지 못함

문제 해결 Key_point

• BFS
• DFS(이번에는 DFS를 이용함)
• 그래프 이론

문제 해결 아이디어

• BFS로 문제를 해결하기 위해, 그림을 입력받을 2차원 벡터와 해당 위치에 방문을 표시할 visited 벡터 생성
• 그림을 입력받고, 일반인의 경우 방문하지 않았다면 DFS를 통해 연결된 부분을 모두 방문처리
  • 이 과정을 반복하여 구역의 개수를 count를 통해 계산
• 적록색약의 경우 r과 g를 구분하지 못하므로, r을 g로 변환한 후 위에 위의 과정을 수행
• 마지막에 각 count들을 출력하면 끝

소스 코드

#include <iostream>
#include <vector>

using namespace std;

vector<int> dx = {-1, 0, 1, 0};
vector<int> dy = {0, 1, 0, -1};

vector<vector<char>> arr; // 원본 그림 배열
vector<vector<bool>> visited; // 방문 여부 저장

int n; // 그리드 크기

// DFS 탐색 함수 (일반인 & 적록색약 구분 X)
void dfs(int x, int y, char color) {
    visited[x][y] = true; //방문표시

    for (int i = 0; i < 4; i++) { // 4방향 탐색
        int nx = x + dx[i];
        int ny = y + dy[i];

        if (nx >= 0 && nx < n && ny >= 0 && ny < n) { // 범위 내에 있고
            if (!visited[nx][ny] && arr[nx][ny] == color) { // 같은 색상이면 탐색
                dfs(nx, ny, color);
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    arr.resize(n, vector<char>(n));
    visited.resize(n, vector<bool>(n, false));

    // 그림 입력 받기
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> arr[i][j];
        }
    }

    int count1 = 0, count2 = 0;

    //일반인 계산
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (!visited[i][j]) { // 방문하지 않은 구역이면 DFS 실행
                dfs(i, j, arr[i][j]);
                count1++;
            }
        }
    }
    for (int i = 0; i < n; i++) { //초기화
        for (int j = 0; j < n; j++) {
            visited[i][j] = false;
        }
    }

    for (int i = 0; i < n; i++) { //적록색약 용으로 변환
        for (int j = 0; j < n; j++) {
            if (arr[i][j] == 'G') {
                arr[i][j] = 'R';
            }
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (!visited[i][j]) {
                dfs(i, j, arr[i][j]);
                count2++;
            }
        }
    }

    cout << count1 << " " << count2 << endl;

    return 0;
}

소감

전형적인 DFS문제이다. 적록색약 계산을 위한 r을 g로 바꾸는 아이디어만 떠올리면 쉽게 해결할 수 있었다.