[BOJ/백준] 2917 늑대 사냥꾼 파이썬

문제 링크 : https://www.acmicpc.net/problem/2917

2917번: 늑대 사냥꾼

 

문제를 잘 이해를 못해서 좀 고민했다.

가장 안전한 길이란  모든 칸에서 나무와 거리의 최솟값이 가장 큰 경로이다. 이 부분에서 최솟값이 가장 큰 경로라길래 최솟값이 가장 크면 가장 작은 값인가 큰값인가 헷갈렸었다. 아주 멍청이 같은 생각이었다.

모든 점에서 나무까지의 거리 중 최소값을 찾아서 저장하고 이동 중에 이 거리가 큰값을 선택해서 가면 된다.

 

모든 점에서 나무까지의 거리는 BFS로 돌리거나 문제에 나와 있는  |R-A| + |C-B| 이 방식으로 거리를 계산하면 된다.

 

모든 점에서 나무까지의 거리를 저장한 다음 이를 가지고 다익스트라로 돌면서 순간마다 거리의 최대값을 갱신하고 오두막에 도착 시 출력하면 된다.

 

from sys import stdin
from collections import deque
import heapq

input = stdin.readline
dx = [-1,1,0,0]
dy = [0,0,-1,1]

n,m = map(int, input().split())

board = []
tree_q = deque()
tree_dist = [[-1]*m for _ in range(n)]
sx=sy=-1

for x in range(n):
    board.append(input().strip())
    for y in range(m):
        if board[x][y] == '+':
            tree_q.appendleft((x,y,0))
            tree_dist[x][y] = 0
        elif board[x][y] == 'V':
            sx,sy = x,y

def solv():
    set_tree_dist()
    print(dijkstra())

def dijkstra():
    answer = 9876543210
    pq = []
    visited = [[False]*m for _ in range(n)]

    heapq.heappush(pq,(-tree_dist[sx][sy],sx,sy))
    visited[sx][sy] = True

    while pq:
        cost,x,y = heapq.heappop(pq)

        answer = min(answer,-cost)

        if board[x][y] == 'J':
            return answer

        for d in range(4):
            for d in range(4):
                nx = x + dx[d]
                ny = y + dy[d]

                if point_validator(nx, ny) and not visited[nx][ny]:
                    visited[nx][ny] = True
                    heapq.heappush(pq,(-tree_dist[nx][ny],nx,ny))

def set_tree_dist():
    global tree_q, tree_dist

    while tree_q:
        x,y,t = tree_q.pop()

        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]

            if point_validator(nx,ny) and tree_dist[nx][ny] == -1:
                tree_dist[nx][ny] = t+1
                tree_q.appendleft((nx,ny,t+1))

def point_validator(x,y):
    if x < 0 or y < 0 or x >= n or y >= m:
        return False
    return True
solv()