[백준 10026] 적록색약 (C++)

1. 문제

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

10026번: 적록색약

 

2. 풀이

아이디어

알고리즘

 

코드

#include<iostream>
#include<queue>
#include<cstring>
#define F first
#define S second
#define IN(Y, X) Y >= 0 && Y < N && X >= 0 && X < N

using namespace std;

queue<pair<int, int>> q;
int dy[4] = {0, 1, 0, -1};
int dx[4] = {1, 0, -1, 0};

int N, board[100][100];
bool visit[100][100];
//R = 34, G = 23, B = 18

void BFS(int y, int x){
    int color = board[y][x];
    visit[y][x] = true;
    q.push({y, x});

    while(!q.empty()){
        pair<int, int> front = {q.front().F, q.front().S};
        q.pop();
        for(int i=0; i<4; i++){
            int ny = front.F + dy[i];
            int nx = front.S + dx[i];
            if(IN(ny, nx) && !visit[ny][nx] && board[ny][nx] == color) {
                visit[ny][nx] = true;
                q.push({ny, nx});
            }
        }
    }
}

int solve(bool blind){
    if(blind) {
        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++) if(board[i][j] == 34) board[i][j] = 23;
        }
    }
    int ret = 0;
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++) if(!visit[i][j]) {
            BFS(i, j);         
            ret++;
        }
    }
    memset(visit, 0, sizeof(visit));
    return ret;

}

int main(void){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    cin >> N;

    for(int i=0; i<N; i++){
        string color;
        cin >> color;
        for(int j = 0; j<N; j++) board[i][j] = color[j] - '0';
    }
    cout << solve(false) << " " << solve(true);

    return 0;
}