Search

[백준 7576] 토마토

[백준 7576] 토마토

Tip

BFS(너비 우선 탐색) 수행
초기에 익은 토마토의 위치들에서부터 탐색 시작
익은 토마토의 위치를 에 삽입
각각 좌표의 그래프 값을 걸린 날짜로 생각
큐에서 값을 꺼내 각각의 위치를 중심으로 상하좌우 방향 옆 위치를 확인
안익은 토마토(0)라면 직전 익은 지점의 날짜값 + 1 값으로 해당 지점의 데이터 갱신
BFS 종료 후 가장 큰 날짜값을 출력
BFS (너비 우선 탐색)?

시간복잡도

인접 행렬로 구현한 그래프에서 BFS 수행시 시간복잡도는 O(NM)
최대 NM개의 지점에서 BFS가 수행이 될 수 있으니 이 문제에선 O((NM)²)
N, M이 각각 최대 1,000으로 최대 NM은 10,000,000으로 시간 초과 우려
탐색에 O(1)의 시간복잡도를 가지는 파이썬의 deque 을 큐 대신 활용하면 → O(NM)으로 시간복잡도를 낮출 수 있음

풀이 소스 코드

import sys from collections import deque si = sys.stdin.readline # 가로 M, 세로 N 입력 m, n = map(int, si().split()) # 토마토 상자 정보 입력 graph = [list(map(int, si().split())) for _ in range(n)] day = 0 # 날짜 초기화 # 확인할 방향 정의(상하좌우) dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] # 초기 토마토의 좌표를 큐에 삽입(익은 토마토만) queue = deque() # 큐 선언에 list보다 빠른 연산 속도를 제공하는 deque 사용 for i in range(n): for j in range(m): if graph[i][j] == 1: queue.append((i, j)) # BFS 함수 (너비 우선 탐색) def bfs(): while queue: # 큐의 가장 왼쪽 요소 빼내어 좌표 확인 x, y = queue.popleft() # 현재 칸에서 상화좌우 방향으로 옆칸 확인 for i in range(4): # 0 ~ 3 nx = x + dx[i] ny = y + dy[i] # 상자 범위 내이고 안익은 토마토가 있는 경우에만 if 0 <= nx < n and 0 <= ny < m and graph[nx][ny] == 0: # 직전 좌표의 요소 값에 1을 더해준 값으로 # 해당 좌표의 토마토가 익기까지 걸린 날짜를 저장 graph[nx][ny] = graph[x][y] + 1 queue.append((nx, ny)) # 해당 좌표를 큐에 삽입 bfs() # BFS 수행 for i in range(n): for j in range(m): # 안익은 토마토가 하나라도 있다면 if graph[i][j] == 0: print(-1) exit(0) # 프로그램 종료 else: day = max(day, graph[i][j]) # 시작할 때 익은 토마토의 값이 1이었기 때문에 최종 계산된 값에 1을 빼주기 print(day - 1)
Python