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

백준 10026 : 적록색약
난이도 : 골드 5

시간 : 17분 소요

 

 

 

문제

https://www.acmicpc.net/problem/10026

10026번: 적록색약

풀이 과정

 

bfs를 사용하면 쉽게 풀 수 있는 문제이다.

적록색약인 경우와 아닌 경우를 구별하기 위해 2개의 함수, 2개의 2차원 배열을 사용했다.

 

적록색약이 아닌 경우에는 방문하지 안한 rgb를 방문하여 인접 노드가 같은 색일 때만 방문처리하고, 큐에 넣는다.

bfs1 함수는 방문하지 않은 노드일 때만 실행되기 때문에 함수를 실행한 수가 영역의 수가 된다.

 

적록색약인 경우는 r과 g를 동등하게 취급해주는 것 외에는 적록색약 아닌 경우와 동일하다.

 

 

 

최종 코드

#include <iostream>
#include <queue>

#define R 82
#define G 71
#define B 66

using namespace::std;

int N;
int rgb[101][101];
int cnt1, cnt2;

int visited_1[101][101];
int visited_2[101][101];

int ud[4] = {-1,1,0,0};
int lr[4] = {0,0,-1,1};

void bfs2(int y, int x, int p){
    visited_2[y][x] = 1;
    queue<pair<int, int>> q;
    q.push({y, x});
    int rg = p;
    if(p == R || p == G){
        rg = R;
        p = G;
    }
    
    while(!q.empty()){
        int ty = q.front().first;
        int tx = q.front().second;
        q.pop();
        
        for(int i=0; i<4; i++){
            int ny = ty + ud[i];
            int nx = tx + lr[i];
            
            if(ny>=1 && nx>=1 && ny<=N && nx<=N){
                if(visited_2[ny][nx] == 0){  // 방문 x, 인접 o
                    if(rgb[ny][nx] == p || rgb[ny][nx] == rg){
                        visited_2[ny][nx] = 1;
                        q.push({ny, nx});
                    }
                }
            }
            
        }
    }
}

void bfs1(int y, int x, int p){
    visited_1[y][x] = 1;
    queue<pair<int, int>> q;
    q.push({y, x});
    
    while(!q.empty()){
        int ty = q.front().first;
        int tx = q.front().second;
        q.pop();
        
        for(int i=0; i<4; i++){
            int ny = ty + ud[i];
            int nx = tx + lr[i];
            
            if(ny>=1 && nx>=1 && ny<=N && nx<=N){
                if(visited_1[ny][nx] == 0 && rgb[ny][nx] == p){  // 방문 x, 인접 o
                    visited_1[ny][nx] = 1;
                    q.push({ny, nx});
                }
            }
        }
    }
}

int main(){
    scanf("%d", &N);
    
    for(int i=1; i<=N; i++){
        string s;
        cin >> s;
        for(int j=1; j<=N; j++){
            rgb[i][j] = s[j-1];
        }
    }
    
    for(int i=1; i<=N; i++){
        for(int j=1; j<=N; j++){
            if(visited_1[i][j] == 0){
                bfs1(i, j, rgb[i][j]);
                cnt1++;
            }
            if(visited_2[i][j] == 0){
                bfs2(i, j, rgb[i][j]);
                cnt2++;
            }
        }
    }
    printf("%d %d\n", cnt1, cnt2);
}

 

 

잡담

카테고리를 모르고 접근해도 쉽게 bfs를 생각할 수 있었다.