이 문제는 전형적인 너비 우선 탐색(Breadth-First Search : BFS) 알고리즘을 활용하는 기본 문제이다.
즉 [x,y] 값을 받아들였을 때, 상하좌우로 이동 후 조건에 맞게 확인하고, 조건에 맞으면 queue에 넣어준 후 방문표시를 해주면 된다.
그리고 queue에 넣는 조건으로는
1. 일단 이동한 후의 x와 y 값이 유효한 위치인지 (y는 H 이하, x는 W 이하)
2. 아직 방문하지 않았는지 (visited[y][x] == 0)
3. 그리고 그 위치에서 색이 똑같은지 (env[y][x] == orig_color)
이 3가지 조건을 확인 후 queue에 넣어주고, 이를 반복 연산하는 코드를 작성해주면 된다.
이 부분은 아래 코드의 주석으로 아주 상세히 설명해놨으니 참고하면 좋을 것 같다.
코드
import sys
from collections import deque
# H (행), W (열) 정보를 받는다.
H, W = map(int, sys.stdin.readline().split())
env = []
# 환경을 받는다.
for _ in range(H):
env.append(list(map(int, sys.stdin.readline().split())))
# bfs 방문여부 행렬을 만든다.
visited = [[0 for _ in range(W)] for _ in range(H)]
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]
def bfs(x,y,c):
# 무효한 위치 거르기
if (x>=W) or (x<0) or (y<0) or (y>=H):
return
# 너비우선탐색을 위한 큐 생성
queue = deque()
# 처음 위치를 넣는다.
queue.append([x,y])
# 처음 색깔을 기록한다.
orig_color = env[y][x]
# 방문처리한다.
visited[y][x] = 1
# 너비우선탐색을 진행한다.
while queue:
# queue에 있는 x,y를 뽑고
nx, ny = queue.popleft()
# 그 위치의 색을 c로 변경한다.
env[ny][nx] = c
# 그리고 위치를 이동하면서 이동한 위치를 queue에 다시 넣어준다.
for i in range(len(dx)):
next_x = x + dx[i]
next_y = y + dy[i]
# 만약 위치가 유효하고, 색이 같으며, 방문하지 않은 경우에만 queue에 넣어준다.
# (방문표시 넣는거 꼭 잊지 말기.)
if (0<=next_y<H) and (0<=next_y<W) and (env[next_y][next_x] == orig_color) and (visited[next_y][next_x]==0):
queue.append([next_x, next_y])
# 그리고 방문표시를 queue에 넣는 코드 바로 뒤에 넣어주는거 잊지 말기.
# 이래야만 중복계산을 방지할 수 있음.
visited[next_y][next_x] = 1
# 연산 갯수 (Q)를 받는다.
Q = int(input())
# 연산을 하나하나 받고 너비우선탐색을 하나하나 돌린다.
for _ in range(Q):
y, x, c = map(int, sys.stdin.readline().split())
bfs(x-1,y-1,c)
# 문자열로 프린트한다.
for line in env:
" ".join(list(map(str, line)))
코드를 짤 때 유의할 점은 방문표시를 queue에 넣을 때 해주어야만 한다. 그렇지 않으면 다음 while 루프에서 이전에 방문한지도 모르고 이전에 방문한 위치를 다시 queue에 넣는 문제를 일으켜 계산 복잡도를 대폭 증가시키게 된다.
