BOJ 10026 · 적록색약

알고리즘 분류 : BFS  

적록색약인과 비색약인이 구별하는 색의 영역 개수를 구하는 문제다. BFS를 통해 구현할 수 있다.

• BFS를 이용하여 맵을 탐색한다.
• 먼저 비색약인으로 모든 영역을 탐색하면서, 영역의 개수를 카운트한다.
• 다음으로 적록색약인으로 모든 영역을 탐색한다.
• 적록색약인의 경우, 적색(R)과 녹색(G)을 같은 색으로 취급한다.

---

C++ 소스코드

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

struct color {
    int x, y;
};

int n;
char a[101][101];
bool check[101][101];
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

// c is color.
// w is a flag about color weakness. true(color weakness) false(none)
void bfs(int i, int j, char c, bool w) {
    queue<color> q;
    q.push({i, j});
    check[i][j] = true;
    while (!q.empty()) {
        int x = q.front().x, y = q.front().y;
        q.pop();
        for (int k=0; k<4; k++) {
            int nx = x+dx[k], ny = y+dy[k];
            if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
            if (check[nx][ny]) continue;
            if (!w && a[nx][ny] != c) continue;
            if (w && (a[nx][ny] == 'R' && c == 'B')) continue;
            if (w && (a[nx][ny] == 'G' && c == 'B')) continue;
            if (w && (a[nx][ny] == 'B' && c != 'B')) continue;
            q.push({nx, ny});
            check[nx][ny] = true;
        }
    }
}

int main() {
    scanf("%d", &n);
    for (int i=0; i<n; i++) {
        scanf("%s", a[i]);
    }
    // None color weakness
    int cnt = 0;
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            if (check[i][j] == false) {
                bfs(i, j, a[i][j], false);
                cnt++;
            }
        }
    }
    printf("%d ", cnt);
    // Color weakness
    cnt = 0;
    memset(check, false, sizeof(check));
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            if (check[i][j] == false) {
                bfs(i, j, a[i][j], true);
                cnt++;
            }
        }
    }
    printf("%d\n", cnt);
    return 0;
}

---

Python 3 소스코드

from collections import deque
from sys import stdin
input = stdin.readline

n = int(input())
a = [list(input().strip()) for _ in range(n)]
check = [[False]*n for _ in range(n)]
dx = (-1, 0, 1, 0)
dy = (0, 1, 0, -1)

def bfs(i, j, c, w):
    q = deque()
    q.append((i, j))
    check[i][j] = True
    while q:
        x, y = q.popleft()
        for k in range(4):
            nx, ny = x+dx[k], y+dy[k]
            if (nx < 0 or nx >= n or ny < 0 or ny >= n) or check[nx][ny]:
                continue
            if w is True and c == 'B' and (a[nx][ny] == 'R' or a[nx][ny] == 'G'):
                continue
            if w is True and c != 'B' and a[nx][ny] == 'B':
                continue
            if w is False and a[nx][ny] != c:
                continue
            q.append((nx, ny))
            check[nx][ny] = True

cnt = 0
for i in range(n):
    for j in range(n):
        if check[i][j] is False:
            bfs(i, j, a[i][j], False)
            cnt += 1
print(cnt, end=' ')
cnt = 0
check = [[False]*n for _ in range(n)]
for i in range(n):
    for j in range(n):
        if check[i][j] is False:
            bfs(i, j, a[i][j], True)
            cnt += 1
print(cnt)

---

참고

• 백준 온라인 저지 : BOJ 10026