[백준] 7576번 토마토 파이썬 해설 (BFS)

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

BFS 알고리즘으로 분류된 문제이다.

코딩 테스트를 통과하기 위해 알고리즘 문제를 많이 풀던 시기에 가장 취약했던 알고리즘의 종류 중 하나이다.

한 번의 시도만에 취업을 성공해서 당분간 코딩 테스트는 치르지 않지만, 약점을 보완하기 위해 내가 약했던 알고리즘을 위주로 문제를 다시 풀어보고 있다.

 

풀이

---

처음 이 문제를 접근할 때는 하루가 지날 때 마다 배열의 모든 점을 탐색하는 알고리즘을 설계하고 그대로 구현하였다.

나름 예외처리를 했다고 생각했지만 M과 N이 증가 할 수록 시간 복잡도가 기하급수적으로 늘어났고 결국 시간 초과라는 결과를 받았다. ㅜㅜ

 

그 후에 파이썬의 dequeue 모듈을 사용해서 좀더 효율적인 알고리즘을 새로 설계했다.

익은 토마토의 좌표만 기억하여 하루가 지날 때 마다 익은 토마토만 선택하여 주변을 탐색하는 알고리즘이다.

 

정답 코드에 대한 알고리즘을 간단하게 설명하면 다음과 같다.

1. 문제에서 주어지는 입력을 배열에 저장하고, 모든 토마토가 익은 상태인지 확인한다.
-> 모든 토마토가 익었다면 0을 출력하고 알고리즘을 종료한다.
2. 모든 토마토가 익지 않았다면, 익은 토마토를 기준으로 영향을 받는 토마토를 탐색한다.
3. 더 이상 영향을 받는 토마토가 없다면 알고리즘을 종료한다.
4. 입력을 받았던 배열을 다시한번 순회하면서 안 익은 토마토가 있는지 확인한다.
-> 안 익은 토마토가 있다면 -1, 익은 토마토가 있다면 지난 일 수를 출력한다.

 

- 정답코드

 

 

import sys
from collections import deque
input = sys.stdin.readline
m, n = map(int, input().split())

arr = []
deq = deque()
visit = [[0 for i in range(m)] for j in range(n)]

for i in range(n):
    arr.append([*map(int, input().split())])

for i in range(n):    
    for j in range(m):
        if arr[i][j] == 1:
            deq.append((i, j))
            visit[i][j] = 1
'''
한 번 배열 전체를 순회하면서 안 익은 토마토가 있는지 확인 한다.
익은 토마토는 존재하고, 안 익은 토마토가 없다면
처음부터 모든 토마토가 익은 상태이기 때문에 0을 출력한다.
'''
flag = 1
for i in range(n):
    for j in range(m):
        if arr[i][j] == 0:
            flag = 0
            break

if flag and deq:
    print(0)
    exit(0)

'''
모든 토마토가 익지 않았다면 하루(단계)를 카운트 하면서 BFS를 수행한다.
이 떄 모든 점을 순회하는게 아니라 익은 토마토를 기준으로, 해당 토마토에게
영향을 받는 부분에 대해서만 BFS를 진행한다.
'''
d_x = [0, 0, 1, -1]
d_y = [1, -1, 0, 0]
ans = 0

while 1:
    deq_second = deque()
    while deq:
        x, y = deq.popleft()
        for i in range(4):
            new_x = x + d_x[i]
            new_y = y + d_y[i]
            if not(0 <= new_x < n and 0 <= new_y < m): continue
            if visit[new_x][new_y] or arr[new_x][new_y] != 0: continue
            deq_second.append((new_x, new_y))
            visit[new_x][new_y] = 1
            arr[new_x][new_y] = 1
    deq = deq_second
    if not deq: break
    ans += 1

#아직 익지 않은 토마토가 있는지 확인하다.
for i in range(n):
    if 0 in arr[i]:
        print(-1)
        exit(0)
print(ans)

*방문을 체크하는 리스트(visit)를 따로 선언하여 중복 순회를 막는다.

 

결과

---

정답 제출 후 다른 사람들의 결과와 비교해보니 아직 많이 부족하다는 것을 알게 되었다.

하지만 시간 초과에 벽에 부딪혔을 때 포기하지 않고 알고리즘을 다시 설계하여 문제를 풀었다는 것에 큰 의미를 두려고 한다.

멋진 개발자가 되기 위해서 더 열심히 해야겠다!