[C++] 백준 10026번: 적록색약

문제

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

 

풀이

BFS로 풀었다.

비장애인과 적록색약의 탐색 함수를 2개 만들어서 풀었다.

 

다른 방법으로는 입력 배열을 2개 만드는 방법이 있다.

• R or G 은 1로 저장
• B는 0으로 저장

이렇게 R과 G를 같은 걸로 취급하면 함수를 1개만 짜도 된다는 장점이 있다. 

 

소스

#include <iostream>
#include <queue>
#include <memory.h>
#define MAX 101
 
char map[MAX][MAX];
bool visited[MAX][MAX];
 
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, -1, 1};
 
bool isValid(int x, int y)
{
    if(x >= MAX || y >= MAX || x < 0 || y < 0)
        return false;
    return true;
}
 
void BFS(int r, int c)
{
    char now = map[r][c];
    std::queue<std::pair<int, int>> q;
    q.push(std::make_pair(r, c));
    
    while(!q.empty())
    {
        for(int i = 0; i < 4; ++i)
        {
            int x = q.front().first + dx[i];
            int y = q.front().second + dy[i];
            
            if(visited[x][y] || !isValid(x, y))
                continue;
            
            if(now == map[x][y])
            {
                q.push(std::make_pair(x, y));
                visited[x][y] = true;
            }
        }
        q.pop();
    }
}
 
void BFS2(int r, int c)
{
    char now = map[r][c];
    bool flag = false;
    
    if(now == 'R' || now == 'G')
        flag = true;
    
    std::queue<std::pair<int, int>> q;
    q.push(std::make_pair(r, c));
    
    while(!q.empty())
    {
        for(int i = 0; i < 4; ++i)
        {
            int x = q.front().first + dx[i];
            int y = q.front().second + dy[i];
            
            if(visited[x][y]|| !isValid(x, y)) continue;
            
            if(flag)
            {
                if(map[x][y] == 'R' || map[x][y] == 'G')
                {
                    q.push(std::make_pair(x, y));
                    visited[x][y] = true;
                }
            }
            else if(now == map[x][y])
            {
                q.push(std::make_pair(x, y));
                visited[x][y] = true;
            }
        }
        q.pop();
    }
}
 
 
int main()
{
    //input
    int N = 0;
    std::cin >> N;
    for(int i=0; i<N; ++i){
        for(int j=0; j<N; ++j){
            std::cin >> map[i][j];
        }
    }
    
    //solve
    int rgb = 0;
    int rg = 0;
    
    //normal
    for(int i=0; i<N; ++i){
        for(int j=0; j<N; ++j){
            if(!visited[i][j])
            {
                BFS(i, j);
                ++rgb;
            }
        }
    }
 
    //2
    memset(visited, false, sizeof(visited));
    for(int i=0; i<N; ++i){
        for(int j=0; j<N; ++j){
            if(!visited[i][j])
            {
                BFS2(i, j);
                ++rg;
            }
        }
    }
    
    //output
    std::cout << rgb <<" "<< rg << std::endl;
    return  0;
}