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

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

10026번: 적록색약

---

문제설명

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

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

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

RRRBB GGBBB BBBRR BBRRR RRRRR

 

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

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

 

 

문제접근

DFS를 사용해 붙어있는 같은 영역을 탐색하고 카운트를 증가시키는 방법으로 영역의 갯수를 구할 수 있다.

이 때, 적록색약에 경우 R과 G를 동일하게 인식해야 하므로, 입력을 받을때 적록색약 배열을 별도로 만들어 R 과 G를 동일한 값으로 저장하면 하나의 DFS로 문제를 해결할 수 있다.

 

 

소스코드

#include <iostream>
#include <vector>
#include <cstdlib>
#include <string.h>
using namespace std;
 
// 일반인 맵
char normalArr[102][102];
 
// 적록색약 맵
char colorBlindArr[102][102];
 
// 일반인 맵 방문 기록
bool normal[102][102];
 
// 적록색약 맵 방문 기록
bool colorBlind[102][102];
 
// 일반인 맵 영역 카운트
int normalCnt = 0;
 
// 적록색약 맵 영역 카운트
int colorBlindCnt = 0;
 
// 좌표 구조체 구현
struct point{
    int x;
    int y;
};
 
// 상하좌우 좌표배열
point pnt[4] = {{-1,0}, {0,-1}, {1,0}, {0, 1}};
 
// 연결된 같은 영역을 탐색하며 방문기록을 저장하는 dfs 함수
void dfs(char (*arr)[102], bool (*board)[102],int row, int col){
    int x, y;
    
    char color = arr[row][col];
    
    // 방문 표시
    board[row][col] = true;
    
    // 현 좌표 기준 상하좌우 연결된 같은 색상이 있는지 탐색
    for(int i=0; i<4; i++){
        x = row + pnt[i].x;
        y = col + pnt[i].y;
        if(arr[x][y] == color && board[x][y] == false){
            dfs(arr,board,x,y);
        }
    }
}
 
int main(){
    freopen("input.txt","r",stdin);
    
    int N;
    cin >> N;
 
    for(int i=1; i<= N; i++){
        for(int j=1; j<= N; j++){
            cin >> normalArr[i][j];
            
            // 적록색약 맵은 G를 R로 바꿔 입력한다.
            if(normalArr[i][j] == 'G'){
                colorBlindArr[i][j] = 'R';
            } else{
                colorBlindArr[i][j] = normalArr[i][j];
            }
        }
    }
    
    // 배열을 순회하며 일반인 영역탐색
    for(int i=1; i<=N; i++){
        for(int j=1; j<=N; j++){
            // 탐색이 안되어있으면 연결영역 전체 탐색
            if(!normal[i][j]){
                dfs(normalArr,normal,i,j);
                // 영역 카운트 증가
                normalCnt++;
            }
        }
    }
    
    // 배열을 순회하며 적록색약 영역탐색
    for(int i=1; i<=N; i++){
        for(int j=1; j<=N; j++){
            // 탐색이 안되어있으면 연결영역 전체 탐색
            if(!colorBlind[i][j]){
                dfs(colorBlindArr,colorBlind,i,j);
                // 영역 카운트 증가
                colorBlindCnt++;
            }
        }
    }
    
    // 결과 출력
    cout << normalCnt << " " << colorBlindCnt;
    
    return 0;
}