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

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

10026번: 적록색약

---

1. Logic

- 딱 봐도 BFS지만 나눠야 하는 부분이 3가지이다.

 

1. 조건을 같지 않을때로 걸고 BFS를 돈다

2. 이후 배열을 순회하며 R 또는 G중 원하는 것을 선택하여 R > G / G > R로 변경해준다.

3. 다시 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]) continue;
            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;
}

---

3. Feedback

- 이번 문제는 보자마자 어떻게 풀지 바로 감이 와서 기분 좋게 풀고 바로 맞췄다!