[Python 파이썬] 백준 17129번 - 윌리암슨수액빨이딱따구리가 정보섬에 올라온 이유

2024년 8월 14일

문제 링크 : 백준 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로 채점하여 맞추신 유일한 분이라 정말 대단하신 분이라 생각했다..!