문제 링크
문제 풀이
- 일반적인 bfs 문제와는 조금 다르게 시작점(익은 토마토)의 위치가 1개 이상이라는 점이다.
- 처음으로 얻은 익은 토마토의 위치를 큐에 넣은 후 너비 우선 탐색을 진행하면, 해당 시작점에 대해 너미 우선 탐색을 모두 진행한다. 이후에 큐에 새로운 익은 토마토의 위치가 추가되고 다시 너비 우선 탐색을 수행해야 할 경우, 기존에 방문한 위치를 다시 방문하는 문제가 발생하므로 다른 방법으로 접근해야 한다.
- 따라서 익은 토마토의 위치는 큐에 모두 넣은 뒤에 너비 우선 탐색을 진행하면 된다.
전체 코드
import sys
from collections import deque
def bfs():
while queue:
x, y = queue.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx < 0 or nx >= n or ny < 0 or ny >= m:
continue
if t[nx][ny] == 0 and not visited[nx][ny]:
t[nx][ny] += t[x][y] + 1
visited[nx][ny] = True
queue.append((nx, ny))
m, n = map(int, sys.stdin.readline().split())
t = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
visited = [[False] * m for _ in range(n)]
queue = deque()
for i in range(n):
for j in range(m):
if t[i][j] == 1:
t[i][j] = 0
queue.append((i, j))
visited[i][j] = True
bfs()
day = 0
for i in t:
if max(i) > day:
day = max(i)
for i in range(n):
for j in range(m):
if t[i][j] == 0:
if not visited[i][j]:
day = -1
print(day)
반응형
'Coding Test > BOJ' 카테고리의 다른 글
[백준/Python] 10026 적록색약 (0) | 2024.02.15 |
---|---|
[백준/Python] 12904 A와 B (2) | 2024.02.14 |
[백준/Python] 2565 전깃줄 (2) | 2024.02.13 |
[백준/Python] 13335 트럭 (2) | 2024.02.12 |
[백준/Python] 2512 예산 (0) | 2024.02.10 |