[백준] 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)

 

 

풀이 방법

이 문제는 DFS(깊이 우선 탐색)로 해결할 수 있다.

 

1.  DFS 탐색 기본 구조:

• 현재 위치에서 상하좌우로 이동하며 연결된 칸을 탐색한다.
• 이미 방문한 칸이거나 배열의 범위를 벗어나면 탐색을 종료한다.

2.  탐색 순서:

• 먼저 일반인의 기준으로 구역을 탐색한다.
• 탐색이 끝난 후, 방문 기록(visited 배열)을 초기화하고, 초록색(G)을 빨간색(R)으로 바꾼 뒤 적록색약 기준으로 다시 탐색한다.

3.  구현 핵심:

• 일반인과 적록색약의 기준을 나누어 2번의 탐색을 수행한다.
• 초록색(G)을 빨간색(R)으로 변환해 적록색약의 관점을 반영한다.

 

풀이 코드

#include <iostream>

using namespace std;
int nx[4] = {1,0,-1,0};
int ny[4] = {0,1,0,-1};
int save[100][100];
bool visited[100][100];
void bfs(int x, int y);
int x, y, n, normal, blindness;
char c;
//R은 1, B는 2, G는 3
int main() {
    cin >> n;
    
    //배열 입력받음
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin >> c;
            if(c=='R') save[i][j] = 1;
            else if(c=='B') save[i][j] = 2;
            else if(c=='G') save[i][j] = 3;
        }
    }
    
    //dfs
    for(int i=0 ;i<n; i++){
        for(int j=0; j<n; j++){
            if(!visited[i][j]) {
                normal++;
                bfs(i,j);
            }
        }
    }
    
    //색맹도 세기 위해 visited배열 초기화 
    //초록색을 빨간색으로 변경
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            visited[i][j] = false;
            if(save[i][j] == 3) save[i][j] = 1;
        } 
    }
    
    //dfs
    for(int i=0 ;i<n; i++){
        for(int j=0; j<n; j++){
            if(!visited[i][j]) {
                blindness++;
                bfs(i,j);
            }
        }
    }
    cout << normal <<" "<<blindness<<'\n';
    return 0;
}

void bfs(int x, int y){
    visited[x][y] = true;
    for(int i=0; i<4; i++){
        int dx = x + nx[i];
        int dy = y + ny[i];
        
        if(dx<0 || dy<0 || dx>=n || dy>=n) continue;
        if(visited[dx][dy]) continue;
        if(save[x][y] != save[dx][dy]) continue;
        bfs(dx, dy);
    }
}