[백준/C++] 10026번: 적록색약(G5)

문제

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

10026번: 적록색약

 

사용한 알고리즘

2022.02.05 - [PS/Algorithm] - [알고리즘 개념정리] 8. 그래프/그래프 탐색

-> 2차원 상에서의 그래프 탐색

 

 

풀이

이차원 상에서의 그래프 탐색이다.
모든 정점에 대해, 그 정점과 입접한 정점은 상, 하, 좌, 우 방향에만 있다.

따라서 각 정점의 좌표 (x,y)에 대해 (x+1, y), (x-1, y), (x, y+1), (x, y-1) 중
특정 조건을 만족하는 것이 인접한 좌표이다.

bfs 시행 횟수를 통해 각 색상 영역의 개수를 알 수 있다. 
적록색약 영역 개수를 구할 때는,
matrix의 'G'를 전부 'R'로 바꾼 후 정상인과 같은 bfs를 한 번 더 돌리면 된다.

 

 

소스코드

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

using namespace std;

int n,ans;
int visited[101][101];
string mat[101];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

void bfs(int x, int y){
    queue<pair<int,int>> q;
    visited[x][y]=1;
    q.push({x,y});

    while(!q.empty()){
        int cur_x=q.front().first;
        int cur_y=q.front().second;
        q.pop();

        for(int i=0; i<4; i++){
            int nx=cur_x+dx[i], ny=cur_y+dy[i];
            if(nx<0 || ny<0 || nx>=n || ny>=n) continue; //경계처리
            if(visited[nx][ny]) continue;
            if(mat[cur_x][cur_y]!=mat[nx][ny]) continue;
            visited[nx][ny]=1;
            q.push({nx,ny});
        }
    }

}
int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    cin>>n;
    for(int i=0; i<n; i++) cin>>mat[i];

    //정상인
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(!visited[i][j]){
                bfs(i,j);
                ans++;
            }
        }
    }
    cout<< ans<<' ';

    //적록색약
    ans=0; //초기화
    memset(visited, 0, sizeof(visited)); //초기화
    for(int i=0; i<n; i++){ //전처리(G를 R로 바꿔주자)
        for(int j=0; j<n; j++){
            if(mat[i][j]=='G')
                mat[i][j]='R';
        }
    }
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(!visited[i][j]){
                bfs(i,j);
                ans++;
            }
        }
    }
    cout<< ans;
    return 0;
}