[백준/Baekjoon] 10026 적록색약 C++ :: BFS

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

10026번: 적록색약

 

---

1. Logic

- BFS함수 안에서 처음 들어갔던 문자와  vec[nexty][nextx]가 같을때만 queue에 push하면 해당되는 구역만 구할 수 있을 것이라고 판단함.

 

- BFS함수의 Logic 대로 정상 BFS를 돈 후 for문을 통해 Red값과 Green값을 똑같은 값으로 만들어주기 위해 for문을 돌아서 R > G 또는 G > R로 변환시킨 후 다시 BFS돈다

 

 

---

 

2. Code

#include<bits/stdc++.h>

using namespace std;

int n;

vector<string> vec(101, "");
vector<vector<bool>> vis(101, vector<bool>(101, false));

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

void BFS(int yy, int xx) {
    queue<pair<int, int>> q;
    q.push({yy, xx});
    vis[yy][xx] = true;

    while(!q.empty()) {
        int x = q.front().second;
        int y = q.front().first;
        q.pop();

        for(int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if(nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
            if(vis[ny][nx]) continue;
            if(vec[ny][nx] != vec[yy][xx]) continue;

            vis[ny][nx] = true;
            q.push({ny, nx});
        }
    }
}

int main() {
    cin >> n;
    int cntRG = 0;
    int cntRGB = 0;

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

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            if(!vis[i][j]) {
                BFS(i, j);
                cntRGB++;
            }
        }
    }

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

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            if(!vis[i][j]) {
                BFS(i, j);
                cntRG++;
            }
        }
    }

    cout << cntRGB << " " << cntRG;
}