[BOJ][Python]7576번 풀이

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

7576번: 토마토

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

def sol(r,c,day):
    if visited[r][c] == True:
        return
    visited[r][c] = True
    for i in range(4):
        if 0<=r+dr[i]<m and 0<=c+dc[i]<n and visited[r+dr[i]][c+dc[i]] == False and t[r+dr[i]][c+dc[i]] == 0:
            q.append((r+dr[i],c+dc[i],day+1))
            t[r+dr[i]][c+dc[i]] = 1
            
dr = [-1,1,0,0]
dc = [0,0,-1,1]    
n,m = map(int, ssr().split())
t = [list(map(int, ssr().split())) for _ in range(m)]
q = deque([])
visited = [[False for _ in range(n)] for _ in range(m)]
for i in range(m):
    for j in range(n):
        if t[i][j] == 1:
            q.append((i,j,0))
ans = 0
while q:
    qr,qc,day = q.popleft()
    sol(qr,qc,day)
    ans = day
for i in range(m):
    for j in range(n):
        if t[i][j] == 0:
            ans = -1
            break
print(ans)

일단 저는 해당 문제를 bfs로 풀었습니다. 보통 이런 그래프 탐색 문제를 풀게 될 때 저는 습관적으로 dfs를 먼저 쓰려고 하는데 최근에 그래프 탐색을 통한 미로 찾기와 비슷한 문제들을 몇 번 풀다 보니 bfs쪽이 알고리즘 구조상 훨씬 빨리 답에 도달한다는 것을 알게 되어서 이제는 이런 문제의 경우 dfs/bfs 중 뭐가 더 나을지 따져보는 경우가 생기는 것 같아 뿌듯하네요.

 

일단 해당 문제는 데이터양이 그렇게 많지가 않습니다. 배열이 커봤자 1000*1000의 데이터를 가지고 있어서 이중 반복문으로 끝까지 다 돌아도 백만번이니 1초면 몇 번이고 돌아도 아무런 문제가 없죠. 따라서 일반적은 bfs를 이용해서 토마토를 익히는 작업을 다 진행한 후에 안익은게 있는지를 체크하는 반복문을 한 번 더 사용해줬습니다. 어차피 두 번을 최대로 다 돌더라도 2백만번이니 아무 문제 없다고 생각했기 때문이죠.

 

문제를 접근하는 방법은 일반적인 bfs문제와 크게 다르지 않기 때문에 큐에 중복되는 데이터가 들어가지 않도록 방문처리를 해주고 걸린 날짜도 함께 튜플로 추가해서 해당 날짜를 답으로 출력해주면 되겠습니다. 골드 문제이긴 하나 크게 어렵지는 않은 문제였던 것 같네요.