[BOJ] 백준 10026 적록색약 c++ 코드 / 풀이

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

10026번: 적록색약

 

 

 

문제설명

적록색약인 사람과 아닌 사람이 보는 그림의 구역 수를 찾는 문제

주어진 그리드에서 연속적으로 색칠된 영역(구역)의 수를 각각 계산해야 함

적록색약이 아닌 사람은 빨간색(R), 초록색(G), 파란색(B)을 모두 구별할 수 있기 때문에, 이들이 본 그림에서 각 색깔별로 구역을 분리하여 계산하고, 적록색약인 사람은 빨간색과 초록색의 차이를 구별하지 못하기 때문에 이 두 색을 동일한 색상으로 간주하여 구역을 계산하여 각각 출력하는 문

 

 

문제풀이

입력 받을 때 원본 배열, 적록색약이 보는 배열을 각각 저장

두 배열 각각에 대해 BFS 탐색을 수행하고 이때 각 탐색은 아직 방문하지 않은 셀에서 시작

탐색을 수행할 때마다 해당 색상의 구역 수를 증가시켜줌

탐색 과정에서 같은 색상이 상하좌우로 인접한 셀을 방문하고, 방문한 셀은 방문 처리

이 과정 모든 셀이 방문될 때까지 반복

 

 

코드설명

사용자로부터 그리드의 크기 n을 입력받고 이후 n행의 문자열을 입력 받으며, 동시에 적록색약인 사람을 위한 그리드를 준비 여기서 초록색('G')을 빨간색('R')로 변경

각각 적록색약이 아닌 사람과 적록색약인 사람을 위한 그리드 탐색을 수행(BFS)

방문하지 않은 노드(셀)에서 시작하여, 해당 색상과 동일한 색상의 인접한 셀들을 방문

이 때 상하좌우로만 이동, 각 BFS 탐색이 시작될 때마다 구역의 수를 1 증가 (ans1 또는 ans2).

 

 

코드

#include <bits/stdc++.h>

#define PRESET ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

/*
    애초에 입력 받을때 적록색약용 입력을 따로 받기 그리고 구역을 순회하면서 방문하지 않은 지점일 경우 BFS(x,y,그칸의 색)으로 BFS돌려서 방문체크 BFS 끝났을때 구역 +
*/

bool visitedRGB[101][101];
bool visitedRB[101][101];
string rgb[101];
string rb[101];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
int n, ans1, ans2;

void bfsForRgb(int x, int y, char c){
    queue<pair<int, int>> q;
    ans1++;

    q.push({x, y});
    visitedRGB[x][y] = true;

    while(!q.empty()){
        auto cur = q.front(); q.pop();

        for(int i = 0; i < 4; i++){
            int nx = cur.first + dx[i];
            int ny = cur.second + dy[i];

            if(nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
            if(visitedRGB[nx][ny] || rgb[nx][ny] != c) continue;

            q.push({nx, ny});
            visitedRGB[nx][ny] = true;
        }

    }
}

void bfsForRb(int x, int y, char c){
    queue<pair<int, int>> q;
    ans2++;

    q.push({x, y});
    visitedRB[x][y] = true;

    while(!q.empty()){
        auto cur = q.front(); q.pop();

        for(int i = 0; i < 4; i++){
            int nx = cur.first + dx[i];
            int ny = cur.second + dy[i];

            if(nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
            if(visitedRB[nx][ny] || rb[nx][ny] != c) continue;

            q.push({nx, ny});
            visitedRB[nx][ny] = true;
        }

    }
}
int main(){
    PRESET;

    cin >> n;

    for(int i = 0; i < n; i++){
        cin >> rgb[i];
        rb[i] = rgb[i];
        if(rb[i].find("G") != rb[i].npos){
            for(int j = 0; j < n; j++){
                if(rb[i][j] == 'G') rb[i][j] = 'R';
            }
        }
    }

    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(!visitedRGB[i][j]){
                bfsForRgb(i, j, rgb[i][j]);
            }
            if(!visitedRB[i][j]){
                bfsForRb(i, j, rb[i][j]);
            }
        }
    }

    cout << ans1 << " " << ans2;
}