[백준] 7576_토마토 (Python)

7576_토마토 (Python)

0. 출처

• 유형 : 그래프 탐색
• 링크 : 7576번: 토마토

1. 기록

• 22/03/25 (금)

2. 풀이

(1) 아이디어, 시간복잡도, 자료구조

1. 아이디어
>> BFS 이용 q에 토마토 위치를 담고  
>> 네 방향으로 익힌뒤 다시 익힌 토마토의 위치를 담고 카운트해준다.

2. 시간복잡도
>> o(v+n) ?

3. 자료구조
>> 이차원배열  
>> BFS  

(2) 예제 입력, 예제 출력

예제 입력 1
6 4
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1

예제 출력 1
8

예제 입력 2
6 4
0 -1 0 0 0 0
-1 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1

예제 출력 2
-1

(3) 풀이

from collections import deque
from pprint import pprint

m, n = map(int, input().split())

a = n # 세로
b = m # 가로

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

# pprint(graph)

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

q = deque()
for i in range(a):
    for j in range(b):
        if graph[i][j] == 1:
            q.append((i,j))

cnt = 0
while q:
    x, y = q.popleft()
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0<=nx<a and 0<=ny<b:
            if graph[nx][ny] == 0:
                graph[nx][ny] = graph[x][y] + 1
                q.append([nx,ny])
            else:
                continue
    cnt += 1

answer = 0
for i in range(a):
    for j in range(b):
        if graph[i][j] == 0:
            print(-1)
            quit()
        answer = max(answer, graph[i][j])

print(answer-1)

(4) 참고 및 정리

처음에 m(가로), n(세로) 순서로 입력되는 것을 x(세로), y(가로) 로 바꿨는데
밑에 부분에서 nx, ny 를 구할 때 x, y 를 직접 사용해서 꼬인 부분이 있었다. 항상 변수 사용에 주의하자!

이중 for 문을 빠져나오기 위해서는 break 를 사용하면 안됩니다.
추가적인 변수를 사용해주거나(흔히 flag = True 등) quit() 또는 exit() 함수를 이용해주면 쉽게 이중for문을탈출할 수 있습니다.

graph 자체에 날짜를 카운트 방법으로 추가적인 이차원 배열이나 변수를 사용하지않아도 되었습니다.
또한 max 함수를 이용해서 최댓값 비교도 손쉽게 할 수 있었습니다.