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

1. 문제 링크

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

17129번: 윌리암슨수액빨이딱따구리가 정보섬에 올라온 이유

 

---

2. 문제 요약

가장 가까운 음식에 도달하면 음식까지의 최단 거리를 출력한다.

---

3. 아이디어 정리

• bfs 사용

1. 2인 경우 최초 큐에 넣어 준다.
2. bfs를 사용하여 가까운 음식에 방문하는 경우 거리를 출력한다.
3. 음식에 방문을 못한 경우 NIE를 출력한다.

---

4. 문제 풀이

4-1. 내 풀이

import sys
from collections import deque

dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]

n, m = map(int, sys.stdin.readline().split())  # 행,열
graph = [list(map(int, list(input()))) for _ in range(n)]

dq = deque()  

for i in range(n):
    for j in range(m):
        if graph[i][j] == 2:
            dq.append((i, j, 0))   # 딱따구리 위치, 거리
            graph[i][j] = 1        # 방문 표시, 장애물로 변경 

while dq:
    x, y, dis = dq.popleft()
    for d in range(4):
        nx = x + dx[d]
        ny = y + dy[d]
        if nx < 0 or ny < 0 or nx >= n or ny >= m:
            continue
        if graph[nx][ny] == 1:   # 방문한 경우 or 장애물
            continue
        if graph[nx][ny] in [3, 4, 5]: # 음식인 경우 그만 
            print("TAK")
            print(dis + 1)
            exit()
        dq.append((nx, ny, dis + 1))
        graph[nx][ny] = 1

print("NIE")

 

---

5. 결론

• bfs를 이용하여 거리를 구하는 문제