풀이 방법

보자마자 bfs 혹은 dfs가 떠올라야 한다.
쉬운 문제이지만, 이 문제에서 시간을 지체했던 이유가 바꿔야 하는 색깔과 현재 색깔이 같은 경우 예외처리를 하지 않아서 시간초과가 떴다.
무슨 말이냐면, 현재 입력 받은 좌표의 색깔이 빨간색이고, 주변 같은 색깔로 이어져있는 타일들을 입력 받은 값 c로 바꿔줘야 하는데, 만약 c가 빨간색이라면 굳이 탐색을 하거나 하지않아도 결과는 빨간색이기 때문이다.
이 경우만 예외 처리를 해준다면 bfs로 풀이했을 때 시간초과가 발생하지 않는다.

풀이 코드

import sys
from collections import deque

h, w = map(int, sys.stdin.readline().split())

ls = []

for i in range(h):
    ls.append(list(map(int, sys.stdin.readline().split())))

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

queue = deque()

for _ in range(q):
    i, j, c = map(int, sys.stdin.readline().split())
    color = ls[i - 1][j - 1]
    if color != c:
        queue.append((i - 1, j - 1))
        ls[i - 1][j - 1] = c

        while queue:
            i, j = queue.popleft()
            dx = [-1, 1, 0, 0]
            dy = [0, 0, -1, 1]

            for index in range(4):
                nx = i + dx[index]
                ny = j + dy[index]
                
                if (nx >= 0 and nx < h) and (ny >= 0 and ny < w):
                    if color == ls[nx][ny]:
                        queue.append((nx, ny))
                        ls[nx][ny] = c


for i in range(h):
    for j in range(w):
        print(ls[i][j], end=" ")
    print()