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

문제

https://www.acmicpc.net/problem/17129

---

문제 설명

1. 0이면 빈 복도여서 지나갈 수 있고, 1이면 장애물로 막혀 지나갈 수 없다.
   1. 윌리암슨수액빨이딱따구리 식구는 2, 청국장은 3, 스시는 4, 맥앤치즈는 5이다.
2. 윌리암슨수액빨이딱따구리는 단위 시간마다 한 칸, 상하좌우로 움직일 수 있다.
3. 시작점은 현재 위치 2이며, 어떤 음식에 가장 빠르게 도착하는지 구한다.
4. "TAK"을 출력 후 음식까지의 최단 거리를 출력한다. 이 때 음식을 먹을 수 없다면 "NIE"를 출력한다.

 

---

풀이

너비 우선 탐색을 이용했다.

 

1. 범위 내에서 해당 위치를 방문하지 않았고, 이동한 위치가 2보다 클 때(해당 위치가 장애물이 아닌 음식이라면)
   "TAK"을 출력하고 최단 거리를 출력한다.
2. 해당 위치가 빈 복도라면 queue에 넣고 방문처리한다.

---

코드

import sys
from collections import deque
input = sys.stdin.readline



n,m = map(int,input().split())
board = [[] for _ in range(n)]

for row in range(n):
    s1 = list(input().strip())
    for col in range(m):
        if s1[col] == '2':
            sy,sx = row,col
        board[row].append(int(s1[col]))


def bfs(sy,sx):
    queue = deque()
    queue.append((sy,sx,0))
    visited = [[0 for _ in range(m)] for _ in range(n)]
    visited[sy][sx] = 1
    dy = [0,1,0,-1]
    dx = [1,0,-1,0]
    while queue:
        y,x,cnt = queue.popleft()
        for i in range(4):
            ny = y+dy[i]
            nx = x+dx[i]
            if -1 < ny < n and -1 < nx < m and not visited[ny][nx]:
                if board[ny][nx] > 2:
                    print("TAK")
                    print(cnt+1)
                    exit()
                elif board[ny][nx] == 0:
                    queue.append((ny,nx,cnt+1))
                    visited[ny][nx] = 1
    print("NIE")
bfs(sy,sx)

---

시간복잡도

• 단순 BFS를 사용하는 문제이다. 인접행렬을 사용했으므로 시간복잡도는 $O(N*M)$이다.
• $N = 3000$, $M = 3000$일 때 최악이므로 약 $O(9*10^6)$의 시간이 걸린다.