[Softeer] 이미지 프로세싱- 파이썬

https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=627 

Softeer

import sys
from collections import deque
sys.setrecursionlimit(10**5)
h, w = map(int,sys.stdin.readline().split())
image = []
for i in range(h):
    image.append(list(map(int,sys.stdin.readline().split())))
q = int(sys.stdin.readline())
dx = [-1,1,0,0]
dy = [0,0,-1,1]
for k in range(q):
    i, j, c = map(int, sys.stdin.readline().split())
    queue = deque()
    old_color = image[i-1][j-1]
    image[i-1][j-1] = c
    queue.append((i-1,j-1))
    while queue:
        x, y = queue.popleft()
        for l in range(4):
            nx = x + dx[l]
            ny = y + dy[l]
            if nx <0 or ny<0 or nx >= h or ny >= w:
                continue
            if image[nx][ny] == old_color:
                image[nx][ny] = c
                queue.append((nx,ny))

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


"""
1 9
1 1 2 2 2 1 1 2 2
2
1 5 1
1 5 2
"""

이렇게 풀면 문제가 있다?

bfs 가 왜 틀리지...?

정답은 맞지만 시간초과가 나온다?

문제가 뭔지 많이 고민했다.

import sys

sys.setrecursionlimit(10**5)
h, w = map(int,sys.stdin.readline().split())
image = [[0]*(w+2)]
for i in range(h):
    image.append([0]+list(map(int,sys.stdin.readline().split()))+[0])
image.append([0]*(w+2))

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

def color(x,y,c):
    oldc = image[x][y]
    image[x][y] = c
    if image[x-1][y] == oldc:
        color(x-1,y,c)
    if image[x+1][y]  == oldc:
        color(x + 1, y, c)
    if image[x][y-1] ==oldc:
        color(x,y-1,c)
    if image[x][y+1] == oldc:
        color(x,y+1,c)
    return

for k in range(q):
    x, y, c = map(int, sys.stdin.readline().split())
    if image[x][y] !=c:
        color(x,y,c)

for i in range(1,h+1):
    for j in range(1,w+1):
        print(image[i][j], end=' ')
    # 이프린트가 조금 신가하다?
    print()

이건 돌아다니는 풀이법인데..?

그냥 dfs로 풀은거 같다. 그리고 재귀를 할때 제한?하는법을 배웠다.