[boj] 백준 10026 적록색약 - BFS

[문제]

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

 

[풀이]

BFS 또는 DFS로 풀 수 있다. 이전 같은 유형의 문제와 비슷하게 같은 색의 약이 들어있는 구역에 대해서 queue에 집어넣어 모두 방문을 해주고, 방문하지 않은 다른 색의 약에 대해 count를 증가시켜주며 구역의 수를 구한다. 적록색 약의 경우 R과 G를 구분하지 못하므로 section 배열을 이 두 약이 같게 취급되도록 변경해준다. visited 배열 초기화하는 것 잊지 말 것! 

 

[코드]

 

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
using namespace::std;

int n;
char section[100][100];

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

bool visited[100][100];

void bfs(int row, int col){
    queue<pair<int,int>> q;
    q.push({row, col});
    visited[row][col] = true;

    while(!q.empty()){
        int r = q.front().first;
        int c = q.front().second;
        q.pop();
        for(int i=0; i<4; i++) {
            int new_r = r + dx[i];
            int new_c = c + dy[i];
            if (new_r < 0 || new_r >= n || new_c < 0 || new_c >= n) continue;
            if(!visited[new_r][new_c] && section[r][c] == section[new_r][new_c]) {
                visited[new_r][new_c] = true;
                q.push({new_r, new_c});
            }
        }
    }

}


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

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

    int cnt = 0, cnt_rg = 0;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(!visited[i][j]){
                bfs(i, j);
                cnt++;
            }
        }
    }

    fill(visited[0], visited[0]+10000, false);

    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(section[i][j]=='G') {
                section[i][j] = 'R';
            }
        }
    }

    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(!visited[i][j]){
                bfs(i, j);
                cnt_rg++;
            }
        }

    }

    cout << cnt << " " << cnt_rg;

}