[Python 파이썬] 백준 17129번 - 윌리암슨수액빨이딱따구리가 정보섬에 올라온 이유
윌리암슨수액빨이딱따구리 세 식구가 정보섬에 올라왔다!
세 윌리암슨수액빨이딱따구리는 정보섬 2층 어딘가에 모여 앉아 쉬고 있었는데, 저 멀리 청국장과 스시와 맥앤치즈가 있는 것을 발견했다! 아빠는 청국장, 엄마는 스시, 아이는 맥앤치즈가 먹고 싶다. 그래서 이 셋은 현위치로부터 가장 가까운 음식을 먹으러 가기로 했다.
정보섬 2층은 An×m의 격자로 표현된다. 어떤 Ai,j가 0이면 빈 복도여서 지나갈 수 있고, 1이면 장애물로 막혀 지나갈 수 없다. 윌리암슨수액빨이딱따구리 식구는 2, 청국장은 3, 스시는 4, 맥앤치즈는 5이다. 윌리암슨수액빨이딱따구리는 단위 시간마다 한 칸, 상하좌우로 움직일 수 있다. 2, 3, 4, 5는 장애물이 아니므로 지나갈 수 있다. 격자 밖으로는 나갈 수 없으며 시작점으로부터 시작점까지의 거리는 0이다. 시작점은 윌리암슨수액빨리딱따구리의 위치, 즉 2의 위치이다.
과연 윌리암슨수액빨이딱따구리 식구는 어떤 음식에 더 빨리 도착할 수 있을까?
입력
첫째 줄에 정보섬 2층의 크기 n과 m이 주어진다. (1 ≤ n,m ≤ 3000, 4 ≤ n×m ≤ 9×106)
이후 n행 m열에 걸쳐 0, 1, 2, 3, 4, 5로만 구성된 Ai,j가 주어진다. Ai,j와 Ai,j+1사이에 공백은 주어지지 않는다.
2, 3, 4, 5는 반드시 하나씩 존재하며 2, 3, 4, 5가 아닌 나머지는 0 또는 1이다.
출력
첫째 줄에 "TAK"(폴란드어로 YES를 의미)을 출력하고, 둘째 줄에 현위치에서 가장 빨리 도착할 수 있는 음식까지의 최단 거리를 출력한다.
아무 음식도 먹을 수 없으면 "NIE"(폴란드어로 NO를 의미)를 출력한다. 이외의 출력은 하지 않는다.
TAK과 NIE를 출력할 때 따옴표는 출력하지 않으며 반드시 대문자로 출력한다.
알고리즘 분류
- 그래프 이론
- 그래프 탐색
- 너비 우선 탐색
문제 접근
암시적 그래프에서의 탐색 문제이며, 최단 거리가 존재하면 해당 거리까지 출력해야 하므로 너비 우선 탐색을 활용하였다.
추가로, 이 문제는 Python3로 채점하여 해결한 사람이 딱 한 분 뿐이다. (어떻게 코드를 짜신 건지 참고하고 싶었으나 비공개 코드라 아쉽게도 참고하지 못했다..)
그래서 이 문제를 파이썬으로 채점하다 시간초과를 겪으셨다면, Pypy3로 채점해보기를 권장드린다!
시작점은 2이며 3, 4, 5는 각기 다른 음식에 매핑되는 숫자이지만 이 문제에서는 쓸모 없는 정보이다.
시작점에서 어느 음식이든 도달할 수 있다면 TAK과 함께 도달할 때까지의 최단 거리를 출력하면 되며,
어느 음식에도 도달할 수 없다면 NIE를 출력하면 된다.
입력 예제
3 3
200
003
045
출력 예제
TAK
3
전체 코드
# 17129
import sys
from collections import deque
input = sys.stdin.readline
def bfs(start_row, start_col):
queue = deque()
# 동 남 서 북
d_row = [0, 1, 0, -1]
d_col = [1, 0, -1, 0]
queue.append([start_row, start_col])
board[start_row][start_col] = "1"
distance = 1
while queue:
for _ in range(len(queue)):
now_row, now_col = queue.popleft()
for i in range(4):
next_row, next_col = now_row + d_row[i], now_col + d_col[i]
if 0 <= next_row < n and 0 <= next_col < m and board[next_row][next_col] != "1":
if board[next_row][next_col] in ("3", "4", "5"):
print("TAK")
print(distance)
return
else:
queue.append([next_row, next_col])
board[next_row][next_col] = "1"
distance += 1
print("NIE")
if __name__ == "__main__":
n, m = map(int, input().split())
board = []
for row in range(n):
now = list(input())
board.append(now)
for col in range(m):
if now[col] == "2":
start_row, start_col = row, col
bfs(start_row, start_col)
풀이 후기
시간초과를 어떻게 해결하지..? 하고 고민하다, 혹시나 해서 Python3로 채점하여 맞은 분들이 얼마나 계신지하고 검색해 보았는데
아하!! 바로 Pypy3로 채점했다..
Python3로 채점하여 맞추신 유일한 분이라 정말 대단하신 분이라 생각했다..!