백준 7576번 파이썬 _ 토마토 (실버1)

www.acmicpc.net/problem/7576

7576번: 토마토

• 문제유형 : BFS
• 문제풀이
  • 주어진 2차원배열을 graph에 저장한다.
  • 초기상태에서 1인 위치를 큐에넣고,  BFS를 통해 인접노드들을 확인하며 0인경우(익지않은 토마토)일때만 1로 바꿔준다.
  • 인접노드는 상하좌우로 움직인 4가지 노드이며, 조건을 통해 그래프 범위를 벗어나지 않도록 체크한다.
  • 여기서는 -1일때는 어차피 아무것도 할수없으므로 신경쓰지 않아도 되고, 0인경우에는 1로 바꿈과 동시에 방문처리가 되므로 굳이 visited배열을 따로 두지 않아도 된다. 
• 개인적으로 기억해야할것들

• BFS는 큐를 이용해야한다.
  • 처음에 큐 안쓰고 그냥 리스트로 했다가 메모리초과남.. (각 라운드별로 리스트를 두고 1라운드때 방문처리된 노드, 2라운드때 방문처리된 노드 만들도록한뒤, 해당리스트를 선형탐색해서 인접노드를 확인하는 방식으로 재귀로 짯는데 암튼 메모리초과남..)
  • 그래서 다시 전형적인 큐를사용한 BFS방식으로 풀었더니 맞았다.
• 자주쓰는 기법(?)인데 생각못한거 
  • BFS에서 라운드마다 1씩 늘리는, 예를들어 전체가 다 방문될때까지 걸린 라운드수, 걸린날짜 등등 세는법
  • 따로 2차원배열을 두고 (걸린시간을 저장할 ), 현재노드(큐에서 pop한 노드) 로부터 방문처리가될 인접노드를 방문처리할때 동시에 +1을 해서 배열에 저장해둔다.
  • 그럼 최종적으로 해당노드가 방문처리될떄의 라운드수가 따로 준비한 2차원배열에 저장되게된다.

day_arr[a + i[0]][b + i[1]] = day_arr[a][b] + 1
day_max = max(day_max, day_arr[a + i[0]][b + i[1]])

 

• 정답코드

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

m,n = map(int, input().split())
graph = []
init = []
day_arr = [[0] * m for _ in range(n)]
day_max = 0
q = deque([])

move = [[-1,0],[1,0],[0,-1],[0,1]] #상하좌우


#graph 입력받기
for i in range(n):
    graph.append(list(map(int, input().split())))

#초기상태에서 1인 상태의 위치확
for j in range(n):
    for k in range(m):
        if graph[j][k] == 1:
            q.append((j,k))


#1의 위치가 담긴 리스트를 인자로 넘겨주면
def solution(q):
    global day_max

    while q:
        curr = q.popleft()
        # print(curr)
        a,b = curr[0], curr[1]

        for i in move: #상하좌우 이동
            if a + i[0] >= 0 and a + i[0] < n and b + i[1] >= 0 and b + i[1] < m:  # 이동가능하면(그래프를벗어나지 않으면)
                if graph[a + i[0]][b + i[1]] == 0:  # 안익은 토마토이면
                    graph[a + i[0]][b + i[1]] = 1  # 익게하고
                    day_arr[a + i[0]][b + i[1]] = day_arr[a][b] + 1
                    day_max = max(day_max, day_arr[a + i[0]][b + i[1]])
                    q.append((a + i[0], b + i[1])) #다음턴을 위한 리스트에 담는다.
    # print(graph)

count = 0

if len(q)==0:
    print(-1)
else:
    solution(q)
    for i in graph:
        if i.count(0) > 0:
            count +=1
            break
    print(-1 if count>0 else day_max)