[Gold 5] 10026번 적록색약

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

10026번: 적록색약

 

이 문제는 DFS를 통해 해결할 수 있다.

알고리즘은 다음과 같다.

색약이 아닌 경우 배열을 순회하고 방문하지 않은 경우 인자로 들어온 x, y의 색과 상, 하, 좌, 우내의 색이 같은 경우

즉, R G B인 경우 탐색을 하여 색의 범위를 찾는다. 색의 범위를 찾았다면 count를 증가시킨다.

 

색약인 경우 먼저 Graph에 있는 G를 R로 바꾼 후 색약이 아닌 경우와 동일하게 탐색을 진행한다.

 

#include <iostream>
#include <queue>
#include <cstring> 
using namespace std;

char graph[100][100];
int visited[100][100] = { 0, };
int count1 = 0, count2 = 0, N;
int dx[] = { 0,0,1,-1 };
int dy[] = { 1, -1, 0 ,0 };
void dfs(int x, int y) {
    visited[x][y] = 1;

    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            int ux = x + dx[i], uy = y + dy[i];
            if (ux < 0 || uy < 0 || ux >= N || uy >= N) continue;

            if (!visited[ux][uy] && graph[x][y] == graph[ux][uy]) {
                dfs(ux, uy);
            }
        }
   }
}

int main() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> graph[i][j];
        }
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (!visited[i][j]) {
                dfs(i, j);
                count1++;
            }
        }
    }

    memset(visited, 0, sizeof(visited)); 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (graph[i][j] == 'G')
                graph[i][j] = 'R';
        }
    }

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

    cout << count1 << ' ' << count2 << '\n';
}