[C++] 백준 BOJ 10026 적록색약

문제링크 : https://boj.kr/10026

현재 위치를 기준으로 상, 하, 좌, 우의 4방향을 DFS로 탐색해서 같은 영역인지 여부를 확인한다.

같은 영역이 아닐 경우 빠져나오며 단 한번이라도 같은 영역이 나오면 true를 반환한다.

시간 복잡도에는 크게 영향이 없을 것 같으나 편의를 위해서 한번 탐색한 'R'은 'G'로 바꿔주도록 했다.

dfs 탐색 도중 중간에서 반환하는 false의 경우는 최초 dfs 실행 후 담을 chk 변수가 아닌 이상 딱히 의미는 없다.

// BOJ 10026 적록색약
#include <bits/stdc++.h>
 
using namespace std;
#define MAXN 101
int num;
char mat[MAXN][MAXN];
bool visited[MAXN][MAXN]; // 방문 체크
const int dir[4][2] = {{0,  -1}, {-1, 0}, {1,  0}, {0,  1}}; // 4방향
 
bool dfs(int x, int y, char input) {
    if (!visited[x][y] && mat[x][y] == input) {
        visited[x][y] = true;
        if(mat[x][y] == 'R')
            mat[x][y] = 'G'; // 다음 탐색(적록색맹)에서 활용하기 위해
        for (int i = 0; i < 4; i++)// 상하좌우 dfs
            dfs(x + dir[i][0], y + dir[i][1], input);
        return true; // 단 한번이라도 input의 색상이 나왔다면 반환
    }
    else
        return false; // 영역이 존재하지 않음
}
 
int calc(char input){
    int result = 0;
    for(int i = 1; i <= num; i++) {
        for (int j = 1; j <= num; j++) {
            bool chk = false;
            chk = dfs(i, j, input);
            if(chk) // 영역이 존재하면
                result++;
        }
    }
    return result;
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    // freopen("../input.txt", "r", stdin);
 
    cin >> num;
    for (int i = 1; i <= num; i++)
        cin >> mat[i] + 1;
 
    int res1 = 0, res2 = 0;
    
    // 1. 안적록색약 실행
    memset(visited, false, sizeof(visited));
    res1 += calc('R');
    res1 += calc('G');
    res1 += calc('B');
    
    // 2. 적록색약 실행 (1 연산시 R->G로 이미 바꿔줬음)
    memset(visited, false, sizeof(visited));
    res2 += calc('G');
    res2 += calc('B');
 
    cout << res1 << " " << res2;
 
    return 0;
}