[백준] 7579번 : 토마토 - Python(파이썬)

문제

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

7576번: 토마토

 

포인트

1. 입력 :

관념적으로 (행, 열)으로 들어지만 해당 문제는 (열, 행)으로 들어옴

M=열, N=행으로 입력 받는 코드 작성하여 헷갈리지 않도록 하자

2. 시작점이 여러 개

미로탈출(백준 2178)과 다르게 익은 토마토(시작점)가 여러개 존재함

여러 시작점에 대한 4방향 탐색 동시에 이뤄져야 함 

익은 토마토가 존재하는 좌표를 모두 que에 넣자

3. 탐색 불필요한 경우 존재

토마토가 존재하지 않는 곳(-1) 이 존재함

별 다른 처리/코드 작성 없이 오직 토마토가 아직 익지 않은 경우(0)에만 기준점+1 되도록 작성

4. Flag=False 사용해 결과값 출력

이중 리스트에 특정 값 존재하면 -1로 결과 나오게 해야 함

방법 1 ) 이중 for문 돌다가 모두 중지하려면 결과값 출력 후 exit(1) 사용

방법 2 ) 이중 for문 돌다가 특정값 나오면 flag=True 로 값 수정

              이후 flag 값에 따라 결과값 출력

5. 이중리스트 내 최대값 출력

map 함수 사용

참고 ) https://devbull.xyz/python-2caweon-baeyeolyi-coedaegabs-coesogabs-cajgi/

Python 2차원 배열의 최대값, 최소값 찾기

 

전체 코드

 

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

M,N=map(int, input().split())
graph=[list(map(int, input().split())) for _ in range(N)]

dx=[1,-1,0,0]
dy=[0,0,1,-1]
que=deque([])
res=0
flag=False

#print(N,M, graph, visited, dx,dy)


for i in range(N):
    for j in range(M):
        if graph[i][j]==1:
            que.append([i,j])

def bfs():
    while que:
        x,y=que.popleft()
        for k in range(4):
            nx, ny=x+dx[k], y+dy[k]
            if 0<=nx<N and 0<=ny<M and graph[nx][ny]==0:
                que.append([nx, ny])
                graph[nx][ny]=graph[x][y]+1


bfs()
for i in range(N):
    for j in range(M):
        if graph[i][j]==0:
            flag=True
            break

if flag:
    print(-1)
else:
    print(max(map(max,graph))-1)