접근

문제 자체는 간단한 BFS 문제였으나, 날짜를 입력하는 새로운 리스트를 만들어서 계산했을 때 시간초과가 나와서 조금 헤메게 되었다.

BFS 연관문제 : 2021.04.11 - [코딩/백준 (Python)] - 백준 2178번: 미로 탐색 (Python)

 

백준 2178번: 미로 탐색 (Python)

접근 문제 설명과 같이 BFS 알고리즘은 해당 위치까지 최단거리로 이동하는 특성이 있다. 예를 들어 첫 칸인 (0, 0)을 탐색할 때 BFS 알고리즘에 따라 현재칸을 기준으로 위, 아래, 왼쪽, 오른쪽 칸

ca.ramel.be

처음에 토마토판을 처음부터 끝까지 탐색하면서 1, 즉 토마토가 있는 칸을 큐에 추가해주었다. 그리고 큐에서 한개씩 popleft 시키면서 해당 칸의 위, 아래, 왼쪽, 오른쪽이 0, 즉 익지않은 토마토일 경우 현재 칸의 숫자보다 1 큰 값을 입력해주게 된다.

마지막으로 전체를 한바퀴 탐색하면서 max값을 탐색하고, 여전히 익지 않은 0이 있을 경우 -1을 출력하도록 해주면 된다.

코드

import sys
from collections import deque

n, m = map(int, sys.stdin.readline().split())
tomato = [list(map(int, sys.stdin.readline().split())) for _ in range(m)]
q = deque([])
for i in range(m):
    for j in range(n):
        if tomato[i][j] == 1:
            q.append([i, j])
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
while q:
    now = q.popleft()
    for i in range(4):
        nx = now[0] + dx[i]
        ny = now[1] + dy[i]
        if 0 <= nx < m and 0 <= ny < n and tomato[nx][ny] == 0:
            tomato[nx][ny] = tomato[now[0]][now[1]] + 1
            q.append([nx, ny])
maximum = 0
all = True
for i in tomato:
    for j in i:
        if j > maximum:
            maximum = j
        if j == 0:
            all = False
if all:
    print(maximum - 1)
else:
    print(-1)

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!

반응형
  • 네이버 블러그 공유하기
  • 네이버 밴드에 공유하기
  • 페이스북 공유하기
  • 카카오스토리 공유하기