2178과 2160을 섞은 문제다.
from collections import deque
import sys
sys.setrecursionlimit(10**6)
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
n = int(sys.stdin.readline())
count = 0
blind_count = 0
color = []
for _ in range(n):
c = list(map(str, sys.stdin.readline()))
color.append(c[:-1])
blind_color = [[('R' if cell == 'G' else cell) for cell in row] for row in color]
visited = [[False]*(n) for _ in range(n)]
def bfs(r, c, my_color):
# global last_r, last_c
q = deque()
q.append((r, c))
while q:
cur_r, cur_c = q.popleft()
visited[cur_r][cur_c] = True
for idx in range(4):
nr = cur_r + dx[idx]
nc = cur_c + dy[idx]
if (0<= nr <n) and (0<= nc < n) and my_color[nr][nc] == my_color[cur_r][cur_c] and not visited[nr][nc]:
visited[nr][nc] = True
q.append((nr, nc))
for i in range(0, n):
for j in range(0, n):
if visited[i][j] == False:
bfs(i, j, color)
count += 1
visited = [[False]*(n) for _ in range(n)]
for i in range(0, n):
for j in range(0, n):
if visited[i][j] == False:
bfs(i, j, blind_color)
blind_count += 1
print(count, blind_count, end=" ")핵심은 사방의 (좌우상하) 값을 보고 같은 지 비교해야 하는 것이다. 처음에 이중포문 없이 구현하겠다고 last_r, last_c를 선언하여 끝나는 지점의 인덱스를 저장하고 한칸 이동하여 다시 search를 했더니 예제의 GG 같은 부분은 책정되지 않았다. (당연함. R -> B를 하고나면 끝나는 지점의 인덱스가 3, 0이기 때문이다.) 그래서 결국 이중포문으로 풀었다. 나는 BFS로 풀었지만 DFS로도 풀 수 있다.
공부