[백준/BOJ] 10026번 - 적록색약 (C++)

문제 링크

 

코딩하기 전 생각하기

/*
큐를 이용한 BFS 방식을 사용하자.
적록색약이 아닌 사람과 적록색약인 사람을 구분하여 board를 두 개 만들자.
각각의 board를 탐색하고 구역을 count한다.
count 값을 출력한다.
*/

 

---

 

코드

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
char board1[101][101]; // non 적록색약 board
char board2[101][101]; // 적록색약 board
bool vis1[101][101]; // non 적록색약 방문
bool vis2[101][101]; // 적록색약 방문
int n;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int cnt1 = 0; // non 적록색약 count
    int cnt2 = 0; // 적록색약 count
    char curr_color1, curr_color2;
    cin >> n;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < n; j++) {
            board1[i][j] = s[j];
            if (s[j] == 'R')
                board2[i][j] = 'G';
            else
                board2[i][j] = s[j];
        }
    }
    queue<pair<int, int>> Q1, Q2;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (vis1[i][j] == 0) {
                cnt1++;
                curr_color1 = board1[i][j];
                vis1[i][j] = 1;
                Q1.push({i, j});
                while (!Q1.empty()) {
                    pair<int, int> cur = Q1.front();
                    Q1.pop();
                    for (int dir = 0; dir < 4; dir++) {
                        int nx = cur.X + dx[dir];
                        int ny = cur.Y + dy[dir];
                        if (nx < 0 || nx >= n || ny < 0 || ny >= n)
                            continue;
                        if (vis1[nx][ny] || board1[nx][ny] != curr_color1)
                            continue;
                        vis1[nx][ny] = 1;
                        Q1.push({nx, ny});
                    }
                }
            }
            if (vis2[i][j] == 0) {
                cnt2++;
                curr_color2 = board2[i][j];
                vis2[i][j] = 1;
                Q2.push({i, j});
                while (!Q2.empty()) {
                    pair<int, int> cur = Q2.front();
                    Q2.pop();
                    for (int dir = 0; dir < 4; dir++) {
                        int nx = cur.X + dx[dir];
                        int ny = cur.Y + dy[dir];
                        if (nx < 0 || nx >= n || ny < 0 || ny >= n)
                            continue;
                        if (vis2[nx][ny] || board2[nx][ny] != curr_color2)
                            continue;
                        vis2[nx][ny] = 1;
                        Q2.push({nx, ny});
                    }
                }
            }
        }
    }
    cout << cnt1 << ' ' << cnt2;
}

 

---

 

느낀점

 

대표적인 그래프 탐색 문제라고 할 수 있겠다.

나는 board를 두 개 만들었지만, 분명 더 효율적인 방법이 있을 것이라고 생각한다.

 

(주의) 기록용으로 작성한 글입니다. 코드가 허접하거나 알고리즘의 효율이 낮을 수 있습니다.

댓글 환영합니다!