[BOJ] 백준 10026번 적록색약 (C++ 코드)

🧨 백준 10026번 적록색약

문제 난이도 : 골드5

문제 링크 : www.acmicpc.net/problem/10026

10026번: 적록색약

🧨 알고리즘 선택 및 C++ 코드

유기농배추 문제와 크게 다를 거 없고, 대신 0과 1의 이분법이 아니라 0, R, G, B를 구분해야 하는 정도가 조금 더 난이도 있다고 볼 수 있다. 여태까지 그래프 관련 문제들 계속 BFS로 구현했어서 이번에는 재귀를 사용한 DFS로 구현했다. 조금 어렵다고 생각했는데 막상 짜보니 별거 아닌 거 같다.

+) 처음에 계속 4가 안 나오고 20이 나오길래 뭐가 문젠가 싶었는데 isMarked와 G 배열을 main에다 선언해주고 파라미터로 전달해서 그랬다. 재귀함수라 전역으로 선언하는 게 맞았다.

+) 1글자씩 입력받는거 저번에 %1d 쓰면 된거 생각나서 이번엔 %1c를 썼다. 근데 한글자만 입력받으니까 줄바꿈 엔터도 인식됐는데, 처음에 이걸 모르고 계속 헤매다가 입력 할 때 scanf("%c", &c); 이거 하나 추가해줬다. 여러모로 좀 오래 걸린 문제였어..

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

int N;
int dx[] = { -1, 1, 0, 0 }; // 좌우상하
int dy[] = { 0, 0, -1, 1 };
int G[100][100] = { 0 };
int isMarked[100][100] = { false };

void recursiveDFS(int x, int y, int color) {
    if (isMarked[x][y]) return;
    else {
        isMarked[x][y] = true;
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
            if (G[nx][ny] == 0) continue;
            if (G[nx][ny] == color && isMarked[nx][ny] == false) {
                recursiveDFS(nx, ny, color);
            }
        }
        return;
    }
}

int main(void) {
    cin >> N;

    char c;
    scanf("%c", &c);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            scanf("%1c", &c);
            if (c == 'R') {
                G[i][j] = 1;
            }
            else if (c == 'G') {
                G[i][j] = 2;
            }
            else {
                G[i][j] = 3;
            }
        }
        scanf("%c", &c);
    }

    int count = 0;
    for (int x = 0; x < N; x++) {
        for (int y = 0; y < N; y++) {
            if (G[x][y] == 0) continue;
            else if (!isMarked[x][y]) {
                recursiveDFS(x, y, G[x][y]);
                count++;
            }
        }
    }
    cout << count << ' ';

    // 2. 적록색약
    count = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            isMarked[i][j] = false;
        }
    }
    for (int x = 0; x < N; x++) {
        for (int y = 0; y < N; y++) {
            if (G[x][y] == 2)
                G[x][y] = 1;
        }
    }

    for (int x = 0; x < N; x++) {
        for (int y = 0; y < N; y++) {
            if (G[x][y] == 0) continue;
            else if (!isMarked[x][y]) {
                recursiveDFS(x, y, G[x][y]);
                count++;
            }
        }
    }
    cout << count << '\n';
}