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

문제: www.acmicpc.net/problem/10026

10026번: 적록색약

 

 

문제풀이

 

BFS 알고리즘 문제이다.

 

큐와 방문여부배열, 영역개수를 2개씩 선언하여 하나는 색약이 아닌 사람 다른 하나는 색약인 사람의 영역 개수를 구하였다.

 

 

코드

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

int dx[4] = {-1,1,0,0};
int dy[4] = {0,0,-1,1};
int visited1[100][100] = {0,};
int visited2[100][100] = {0,};
string board[100];

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    
    int n;
    cin>>n;

    for(int i=0; i<n; i++){
        cin>>board[i];
    }

    int cnt1 = 0;
    int cnt2 = 0;
    queue<pair<int,int>> q1;
    queue<pair<int,int>> q2;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(visited1[i][j] == 0){ //색약x
                q1.push({i,j});
                visited1[i][j] = 1;
                cnt1++;
            }

            if(visited2[i][j] == 0){ //색약o
                q2.push({i,j});
                visited2[i][j] = 1;
                cnt2++;
            }

            while(!q1.empty()){
                pair<int,int> cur = q1.front();
                q1.pop();

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

                    if(nx<0||nx>=n||ny<0||ny>=n) continue;
                    if(visited1[nx][ny]||board[cur.first][cur.second] != board[nx][ny]) continue;

                    visited1[nx][ny] = 1;
                    q1.push({nx,ny});
                }
            }

            while(!q2.empty()){
                pair<int,int> cur = q2.front();
                q2.pop();

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

                    if(nx<0||nx>=n||ny<0||ny>=n) continue;
                    if(visited2[nx][ny]) continue;
                    if((board[cur.first][cur.second] == 'B' || board[nx][ny] == 'B') && board[cur.first][cur.second] != board[nx][ny]) continue;

                    visited2[nx][ny] = 1;
                    q2.push({nx,ny});
                }
            }            
        }
    }

    cout<<cnt1<<" "<<cnt2;


    return 0;
}

 

 

결과