7576 토마토 _python

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

7576번: 토마토

 

색칠공부?

불편한게 있다면 N과 M을 보통 백준 문제와는 다르게 거꾸로 입력받는다... 아;

 

 

 

 

문제 풀이

쿼리도를 만들면서 이동가능한지 체크할때 어떤 알고리즘을 쓸지 고민하다가 Flood fill 이라는 알고리즘을 알게되서 사용했다.

이 문제를 보자말자 내가 썼던거랑 완전 똑같이 풀면 되겠는데? Flood fill문제네! 했다.

https://portable-paper.tistory.com/29?category=970607 

[쿼리도 만들기] 3. wall에 Flood Fill적용하기

하핳

 

가능한 모든 경우를 색칠해나가는 알고리즘으로 진짜 색칠공부다.

위키를 보면 이해하기 쉽다.

https://ko.wikipedia.org/wiki/%ED%94%8C%EB%9F%AC%EB%93%9C_%ED%95%84

플러드 필 - 위키백과, 우리 모두의 백과사전

굳이 들어가지 않아도 gif로 보이는 색칠하는 과정으로도 충분하고,

링크안에 queue와 stack으로 구현하는 예시도 있다.

queue로 구현하는것이 좋다고도 나와있다.

 

 

 

 

풀이

from collections import deque
import sys
input = sys.stdin.readline

"""
Flood Fill알고리즘 사용
1. 1이 여러개인 경우가 있으니 1을 찾아서 위치를 append
2. Flood fill로 모두 색칠
2-1. 색칠하면서 1씩 더해줌.
3. 색칠후, 0이 있다면 -1출력, 아니면 max출력

"""

#입력, 변수선언
M, N = map(int,input().split())
arr = []
for i in range(N):
    arr.append(list(map(int,input().split())))
queue = deque()
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
ans = 0

# 1. 1이 여러개인 경우가 있으니 1을 찾아서 위치를 append
for i in range(N):
    for j in range(M):
        if arr[i][j] == 1:
            queue.append([i,j])

#2. Flood fill로 모두 색칠
#2-1. 색칠하면서 1씩 더해줌.
while queue:
    x,y = queue.popleft()

    for i in range(4):
        xi = x + dx[i]
        yi = y + dy[i]
        if 0<=xi<N and 0<=yi<M:
            if arr[xi][yi] == 0:
                arr[xi][yi] = arr[x][y] + 1
                queue.append([xi,yi])

#3. 색칠후, 0이 있다면 -1출력, 아니면 max출력
for i in range(N):
    for j in range(M):
        if arr[i][j] == 0:
            ans = -1
    if ans!=-1:
        maxVal = max(*arr[i])-1
        if ans<maxVal:
            ans = maxVal

print(ans)

2844ms

pypy3는 588ms