[백준][Python][10026][BFS] 적록색약

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

10026번: 적록색약

BFS 문제다.

 

물론 더 효율적이고 간단한 방법은 분명히 있을 것이다.

하지만 난 일단 맞으면 끝이라는 정신으로 문제를 풀기 때문에 더 안 할 것이다.

 

나는 문제를 bfs를 두 번 돌리는 식으로 풀었다.

이문제는 https://www.acmicpc.net/problem/1012, https://www.acmicpc.net/problem/2667, 이런 문제들처럼 구역의 개수를 구하는 것이다. 다른 점은, 한 번은 R-G, B 이렇게 두 개의 그룹으로 나눠야 하고, 다음번에는 R, G, B 세 개의 그룹으로 나눠야 한다는 것이다.

그래서 난 bfs를 위 규칙에 따라 두 번 돌려서 해결했다.

import sys
from collections import deque

n = int(sys.stdin.readline())

m = []

dy, dx = [1, -1, 0, 0], [0, 0, 1, -1]

for _ in range(n):
    m.append([i for i in sys.stdin.readline().strip()])

ans = [0, 0]
# r-g, b
v = [[-1] * n for _ in range(n)]
ret = 0
for i in range(n):
    for j in range(n):
        q = deque()
        if m[i][j] == "R" or m[i][j] == "G":
            if v[i][j] == -1:
                v[i][j] = ret
                q.append((i, j))

                while q:
                    cy, cx = q.popleft()
                    for k in range(4):
                        ty, tx = cy+dy[k], cx+dx[k]
                        if 0 <= ty < n and 0 <= tx < n:
                            if v[ty][tx] == -1 and (m[ty][tx] == "R" or m[ty][tx] == "G"):
                                v[ty][tx] = ret
                                q.append([ty, tx])
            else:
                continue
        else:
            if v[i][j] == -1:
                v[i][j] = ret
                q.append((i, j))

                while q:
                    cy, cx = q.popleft()
                    for k in range(4):
                        ty, tx = cy+dy[k], cx+dx[k]
                        if 0 <= ty < n and 0 <= tx < n:
                            if v[ty][tx] == -1 and m[ty][tx] == m[cy][cx]:
                                v[ty][tx] = ret
                                q.append([ty, tx])

            else:
                continue

        ret += 1
ans[0] = ret
# r g b
v = [[-1] * n for _ in range(n)]
ret = 0
for i in range(n):
    for j in range(n):
        q = deque()

        if v[i][j] == -1:
            v[i][j] = ret
            q.append((i, j))

            while q:
                cy, cx = q.popleft()
                for k in range(4):
                    ty, tx = cy+dy[k], cx+dx[k]
                    if 0 <= ty < n and 0 <= tx < n:
                        if v[ty][tx] == -1 and m[ty][tx] == m[cy][cx]:
                            v[ty][tx] = ret
                            q.append([ty, tx])
        else:
            continue
        ret += 1


ans[1] = ret


print(" ".join(str(i) for i in reversed(ans)).strip())