[softeer] [21년 재직자 대회 예선] 이미지 프로세싱 (python)

https://softeer.ai/practice/info.do?idx=1&eid=627 

Softeer

---

문제 회고

image의 크기가 크지 않아서 입력을 받을 때마다 bfs를 통해서 색깔을 모두 바꿔주었다.

하지만 계속 히든 케이스에서 시간 초과가 나서 좀 찾아봤더니 만약 x, y, c를 입력받았는데 (x, y)의 색깔이 c와 같다면 무한 loop를 돌게 되어서 시간 초과가 나는 것이었다.

간단하게 시작 지점에서 해당 좌표의 색이 바꾸려는 색과 같은지 조건문 하나만 넣어 간단하게 해결하였다.

---

import sys
from collections import deque

dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

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

q = int(sys.stdin.readline())
for _ in range(q):
    x, y, c = map(int, sys.stdin.readline().split())
    now = image[x][y]
    if now == c:
        continue
    q = deque()
    image[x][y] = c
    q.append((x, y))
    while q:
        i, j = q.popleft()
        for k in range(4):
            nx, ny = i + dx[k], j + dy[k]
            if 1 <= nx <= h and 1 <= ny <= w:
                if image[nx][ny] == now:
                    image[nx][ny] = c
                    q.append((nx, ny))

for i in range(1, h + 1):
    print(' '.join(map(str, image[i][1:])))