[백준/Baekjoon 7576] 토마토 파이썬(Python)풀이

문제

 

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

7576번: 토마토

 

문제 핵심

 이번 토마토 문제의 경우 전형적인 BFS문제이다. 여기서 고려해야 할 것 먼저 (1) 익은 토마토를 찾고 (2) bfs를 이용하여 빈자리를 제외한 토마토를 익히는 것이다. (3) bfs를 진행후 토마토가 다 익었는지 확인해야한다.

 

풀이과정

1. M,N과 2차원 토마토를 넣을 tomato =  [] 를 선언한다.

2. 좌표를 이용한 bfs이므로 dx, dy를 입력받는다.

3. 반복문을 통해 tomato 리스트 입력을 받는다.

4. queue를 선언하고 반복문을 통해 tomato[i][j]==1일 대 queue에 [i,j]를 넣는다.

5. bfs를 진행시킨다.

6. 토마토가 익었는지 확인할 변수 fresh를 선언후 반복문을 통해 토마토가 다 익었는지 확인한다.

7. 다 익었으면 최대값을 익지 않았으면 -1을 출력한다.

 

#bfs 함수

-> 기존 bfs를 이용한다. 

 

정답코드

from collections import deque

def bfs():
    while queue:
        x,y = queue.popleft()
        
        for i in range(4):
            X = x+dx[i]
            Y = y+dy[i]
            if 0 <= X <N and 0<= Y <M and tomato[X][Y]==0:
                queue.append((X,Y))
                tomato[X][Y] = tomato[x][y] +1


M,N = map(int,input().split()) # N = y, M = x
tomato = []
dx = [0,0,1,-1]
dy = [1,-1,0,0]

for i in range(N):
    tomato.append(list(map(int,input().split())))

queue = deque()
for i in range(N):
    for j in range(M):
        if tomato[i][j]==1:#토마토가 익어있으면 queue에 집어 넣기
            queue.append([i,j])

bfs()
fresh = False   
for a in range(N):
    for b in range(M):
        if tomato[a][b] ==0:
            fresh = True
            break

if fresh:
    print(-1)
else:
    print(max(max(row) for row in tomato)-1)

 

문제평 및 새롭게 알게된 것

전형적인 bfs문제여서 풀기에는 틀을 잡는데에는 어렵지 않았다.

bfs함수에서 X,Y를 M,N 중 어디에 대응해야하는지 약간 헷갈렸다.

마지막 최대값을 구하는데에 있어서 max(max(tomato))를 하면 계속 오답이 나온다는 것을 알게되었다.

 

max(max(tomato))의 경우 각 하위리스트들의 첫 원소크기를 비교한 후 max를 적용한다.
max(max(row) for row in tomato))의 경우 하위리스트중 가장 큰수들을 찾아낸 후 max를 적용한다.
->
max(max()) : 하위 리스트 비교후 큰 리스트에서 큰 수 찾기
max(max(row) for row in tomato)) : 각각의 하위 리스트에서 큰수를 찾은 후 각 찾은 리스트에서 큰 수 찾기 

위의 예시

a = [[1,2,3,4,13],[7,8,9,12,11]]
print(max(max(a)))
print(max([max(row) for row in a]))

위 코드를 진행해볼경우 두개의 print의 결과를 확인해보길 바란다.