취준/백준
[백준][Python][10026][BFS] 적록색약
puff
2020. 5. 1. 20:44
문제 : https://www.acmicpc.net/problem/10026
10026번: 적록색약
문제 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은
www.acmicpc.net
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())