10026

백준 10026번

Link: 10026번: 적록색약

---

문제 설명

이번에도 BFS 문제.

각각의 색깔명에 대해 전체 map이 몇개의 영역으로 나눠지는지 구하는 문제였다.

한가지 특이했던 점은 적록색맹이라는 상황을 줌으로써 R값과 G값을 같은 값으로 보고 풀어야 하는 부분이 존재했다는 점.

적록색맹이 아닌 사람과 적록색맹인 사람의 경우를 따로 나눠 구해야 한다.

처음에는 map을 아예 새로 만들까 했었는데, 조건문에서 R과 G에 대한 조건을 or로 묶으니 굳이 안그래도 해결됐다.

---

정답 코드

//
// Created by Keith_Lee on 28/01/2019.
//

#include <iostream>
#include <queue>
#include <string.h>

using namespace std;

int N;
char map[101][101];
bool visit[101][101];

int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

int normalResult = 0;
int redGreenResult = 0;

void BFS_normal(int startX, int startY){
    queue<pair<int, int>> Queue;

    Queue.push(make_pair(startX, startY));
    visit[startX][startY] = true;

    while(!Queue.empty()){
        int currentX = Queue.front().first;
        int currentY = Queue.front().second;
        Queue.pop();

        for(int i=0; i<4; i++){
            int nextX = currentX + dx[i];
            int nextY = currentY + dy[i];

            if(nextX >= 1 && nextX <= N && nextY >= 0 && nextY <= N){
                if(map[startX][startY] == 'R'){
                    if(map[nextX][nextY] == 'R' && !visit[nextX][nextY]){
                        visit[nextX][nextY] = true;
                        Queue.push(make_pair(nextX, nextY));
                    }
                }
                else if(map[startX][startY] == 'G'){
                    if(map[nextX][nextY] == 'G' && !visit[nextX][nextY]){
                        visit[nextX][nextY] = true;
                        Queue.push(make_pair(nextX, nextY));
                    }
                }
                else if(map[startX][startY] == 'B'){
                    if(map[nextX][nextY] == 'B' && !visit[nextX][nextY]){
                        visit[nextX][nextY] = true;
                        Queue.push(make_pair(nextX, nextY));
                    }
                }
            }
        }
    }

    normalResult++;
}

void BFS_redGreen(int startX, int startY){
    queue<pair<int, int>> Queue;

    Queue.push(make_pair(startX, startY));
    visit[startX][startY] = true;

    while(!Queue.empty()){
        int currentX = Queue.front().first;
        int currentY = Queue.front().second;
        Queue.pop();

        for(int i=0; i<4; i++){
            int nextX = currentX + dx[i];
            int nextY = currentY + dy[i];

            if(nextX >= 1 && nextX <= N && nextY >= 0 && nextY <= N){
                if(map[startX][startY] == 'R' || map[startX][startY] == 'G'){
                    if((map[nextX][nextY] == 'R' || map[nextX][nextY] == 'G') && !visit[nextX][nextY]){
                        visit[nextX][nextY] = true;
                        Queue.push(make_pair(nextX, nextY));
                    }
                }
                else if(map[startX][startY] == 'B'){
                    if(map[nextX][nextY] == 'B' && !visit[nextX][nextY]){
                        visit[nextX][nextY] = true;
                        Queue.push(make_pair(nextX, nextY));
                    }
                }
            }
        }
    }

    redGreenResult++;
}

int main(){
    cin >> N;

    for(int i=1; i<=N; i++){
        for(int j=1; j<=N; j++){
            cin >> map[i][j];
        }
    }

    for(int i=1; i<=N; i++){
        for(int j=1; j<=N; j++){
            if(!visit[i][j]){
                BFS_normal(i, j);
            }
        }
    }

    bzero(visit, sizeof(visit));

    for(int i=1; i<=N; i++){
        for(int j=1; j<=N; j++){
            if(!visit[i][j]){
                BFS_redGreen(i, j);
            }
        }
    }

    cout << normalResult << ' ' << redGreenResult << '\n';

    return 0;
}

---