[백준 / python] 15240번 Paint bucket

https://www.acmicpc.net/problem/15240

15240번: Paint bucket

문제

One of the most time-saving operations when drawing on a computer (for example using Photoshop) is the “bucket fill”  operation.

When you select this tool and click on a (target) pixel of the image it will fill all the pixels that have the same color than the target pixel and are connected to it. Two pixels are connected if they share a side or if they are connected through a path of connected pixels.

Let’s see an example: In the following image, if we select the “fill” operation in an image editor program and click on the center of the image (orange pixel). The whole region will be painted orange. Notice that the pixels are not connected diagonally so two corners of the image remain white.

 

Your task is: Given a matrix of digits representing the pixels, simulated what would be the result of a “fill” operation on given pixels. Thus, the colors will be represented with a number from 0 to 9.

Let’s see another example, now using digits instead of pixels. We have the following image:

0000000
0111000
0111010
0000000

If we “fill” at position Y = 0, X = 0 with color 3, all the 0s get painted of color 3. Because all of them are recursively connected.

The result will be:

3333333
3111333
3111313
3333333

입력

The first line will contain two integers R and C representing the number of rows and columns of the image.

The next R lines will contain C digits each representing the initial colors of the pixels.

The last line will contain 3 integers Y, X and K representing the row and column where we want to apply the “fill” operation and the color to use.

The images will be smaller than 1000 x 1000 pixels.

The colors are limited to a single digit from 0 to 9.

출력

Print the resulting image after applying the operation in the same format as the input.

문제풀이

dfs로 풀면 시간초과가 나서 bfs로 풀어보니 메모리초과가 났다...

1. 재귀 깊이 설정 후 dfs 시간 초과
2. BFS로 변경: DFS는 절대로 최단거리를 구해주지 않습니다. 물론 메모이제이션 없이 모든 경로를 탐색하는 DFS는 최단거리를 구해주겠지만, 시간 초과가 날 것
3. BFS 메모리 초과: 큐에서 뺀 다음이 아닌, 큐에 넣을 때 방문 체크를 해야 중복 방문이 일어나지 않습니다. 그래도 메모리 초과가 뜰 경우 방문체크용 matrix를 따로 만들어서 중복 반복을 방지

from collections import deque

def bfs(y, x, K):
    q.append((y, x))
    n = graph[y][x]
    visited[y][x] = 1
    graph[y][x] = K
    while q:
        y, x = q.popleft()
        for dy, dx in d:
            Y, X = y+dy, x+dx
            if (0 <= Y < R) and (0 <= X < C) and graph[Y][X] == n and not visited[Y][X]:
                graph[Y][X] = K
                visited[Y][X] = 1 
                q.append((Y, X))
                

R, C = map(int, input().split())
graph = [list(input()) for _ in range(R)]
Y, X, K = map(int, input().split())

visited = [[0] * C for _ in range(R)]
d = [(0, 1), (0, -1), (1, 0), (-1, 0)]
q = deque()
bfs(Y, X, str(K))
for line in graph:
    print(''.join(line))