[파이썬] 백준 2917 : 늑대사냥꾼 (골드2)

[파이썬] 백준 2917 : 늑대사냥꾼 (골드2)

• https://www.acmicpc.net/problem/2917

---

풀이

방향성 생각

• BFS로 거리 계산 후 다익스트라

 

---

전체코드

from collections import deque
import heapq as hq
import sys
input = lambda : sys.stdin.readline().rstrip()
dire = [(1,0),(0,1),(-1,0),(0,-1)]
inside = lambda x,y : 0<=x<W and 0<=y<H
INF = sys.maxsize

H,W = map(int,input().split())
arr = [input() for _ in range(H)]

# 나무위치, 시작점, 도착점 찾기
Q = deque()
tree_dist = [[-1]*W for _ in range(H)]
for i in range(H):
    for j in range(W):
        if arr[i][j] == '+':
            Q.append((j,i))
            tree_dist[i][j] = 0
        elif arr[i][j] == 'V':
            sx,sy = j,i
        elif arr[i][j] == 'J':
            ex,ey = j,i

# 나무 기준 BFS 돌려서 거리 구하기
while Q:
    x,y = Q.popleft()
    for dx,dy in dire:
        nx,ny = x+dx,y+dy
        if inside(nx,ny) and tree_dist[ny][nx] == -1 and arr[ny][nx] != '+':
            tree_dist[ny][nx] = tree_dist[y][x] + 1
            Q.append((nx,ny))

# 최대힙으로 
heap = [(-tree_dist[sy][sx],sx,sy)]
V = [[-INF]*W for _ in range(H)]
V[sy][sx] = tree_dist[sy][sx]

while heap:
    d,x,y = hq.heappop(heap)
    d = -d

    if d < V[y][x]:
        continue

    for dx,dy in dire:
        nx,ny = x+dx,y+dy
        if inside(nx,ny):
            nd = min(d,tree_dist[ny][nx])
            if nd > V[ny][nx]:
                V[ny][nx] = nd
                hq.heappush(heap,(-nd,nx,ny))

print(V[ey][ex])

---

코멘트

• .