[백준] 10026번: 적록색약 - C++

문제 출처:https://www.acmicpc.net/problem/10026

---

문제

적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다.

크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다)

예를 들어, 그림이 아래와 같은 경우에

RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 하지만, 적록색약인 사람은 구역을 3개 볼 수 있다. (빨강-초록 2, 파랑 1)

그림이 입력으로 주어졌을 때, 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100)

둘째 줄부터 N개 줄에는 그림이 주어진다.

출력

적록색약이 아닌 사람이 봤을 때의 구역의 개수와 적록색약인 사람이 봤을 때의 구역의 수를 공백으로 구분해 출력한다.

DFS, BFS 알고리즘을 이용하는 기초적인 문제입니다.

배열에서 R, G, B 각각의 영역 갯수를 구하는 문제인데 제약조건이 하나 붙습니다.

R, G, B에 대한 영역 (R, G), B에 대한 영역 갯수 2가지를 구하여야 합니다.

저는 처음부터 2차원 배열을 2개 만들어서 입력받을때 한 배열은 R, G, B 그대로 만들고

다른 배열은 (R, G)를 같은 영역으로 입력받아 그 2개의 배열에 각각 DFS 알고리즘을

수행하여 영역의 갯수를 구하는 방식으로 문제를 풀었습니다.

입력받을때 2가지 배열로 나누어 입력받는 코드입니다.

for (int i = 0; i < n; i++) { cin >> str; for (int j = 0; j < n; j++) { switch (str[j]) { case 'R': arr1[i][j] = 1; arr2[i][j] = 1; break; case 'G': arr1[i][j] = 2; arr2[i][j] = 1; break; case 'B': arr1[i][j] = 3; arr2[i][j] = 2; break; } } }

영역의 크기를 구해주는 DFS알고리즘 코드 입니다.

void DFS(int **arr, int num, int x, int y) { arr[y][x] = 0; if (y > 0 && arr[y - 1][x] == num) DFS(arr, num, x, y - 1); if (y < n - 1 && arr[y + 1][x] == num) DFS(arr, num, x, y + 1); if (x > 0 && arr[y][x - 1] == num) DFS(arr, num, x - 1, y); if (x < n - 1 && arr[y][x + 1] == num) DFS(arr, num, x + 1, y); }

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string>
 
using namespace std;
int count1 = 0, count2 = 0, n;
 
void DFS(int **arr, int num, int x, int y) {
    arr[y][x] = 0;
    if (y > 0 && arr[y - 1][x] == num)
        DFS(arr, num, x, y - 1);
    if (y < n - 1 && arr[y + 1][x] == num)
        DFS(arr, num, x, y + 1);
    if (x > 0 && arr[y][x - 1] == num)
        DFS(arr, num, x - 1, y);
    if (x < n - 1 && arr[y][x + 1] == num)
        DFS(arr, num, x + 1, y);
}
 
int main() {
    string str;
    scanf("%d", &n);
    int **arr1 = new int*[n], **arr2 = new int*[n];
 
    for (int i = 0; i < n; i++) {
        arr1[i] = new int[n];
        arr2[i] = new int[n];
    }
 
    for (int i = 0; i < n; i++) {
        cin >> str;
        for (int j = 0; j < n; j++) {
            switch (str[j])
            {
            case 'R':
                arr1[i][j] = 1;
                arr2[i][j] = 1;
                break;
            case 'G':
                arr1[i][j] = 2;
                arr2[i][j] = 1;
                break;
            case 'B':
                arr1[i][j] = 3;
                arr2[i][j] = 2;
                break;
            }
        }
    }
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (arr1[i][j] != 0) {
                count1++;
                DFS(arr1, arr1[i][j], j, i);
            }
            if (arr2[i][j] != 0) {
                count2++;
                DFS(arr2, arr2[i][j], j, i);
            }
        }
    }
    printf("%d %d", count1, count2);
    return 0;
}