이번 문제는 BFS와 다익스트라 알고리즘을 활용하여 해결하였다. 나무들의 좌표를 저장하고, 이를 이용하여 BFS를 통해 모든 좌표의 나무까지의 최소 거리를 저장한 리스트를 만들었다. 그리고 다익스트라 알고리즘을 활용하여 이 나무까지의 최소 거리 리스트의 값들을 통해 거쳐가는 최소 가중치를 구하도록 하였다.

Code

import heapq
from collections import deque
n, m = map(int, input().split())
grid = [list(str(input())) for _ in range(n)]
sy, sx = 0, 0
trees = deque()
trees_dists = [[-1 for _ in range(m)] for _ in range(n)]
for i in range(n):
    for j in range(m):
        if grid[i][j] == 'V':
            sy, sx = i, j
        if grid[i][j] == '+':
            trees.append((i, j, 0))
            trees_dists[i][j] = 0
dy, dx = [0, 1, 0, -1], [1, 0, -1, 0]
def between_tree_and_me():
    while trees:
        y, x, dist = trees.popleft()
        for i in range(4):
            ny, nx = y+dy[i], x+dx[i]
            if 0 <= ny < n and 0 <= nx < m and trees_dists[ny][nx] == -1:
                trees_dists[ny][nx] = dist+1
                trees.append((ny, nx, dist+1))
def go_to_J():
    q = []
    heapq.heappush(q, (-trees_dists[sy][sx], sy, sx))
    visited = [[False for _ in range(m)] for _ in range(n)]
    visited[sy][sx] = True
    result = 1e9
    while q:
        td, y, x = heapq.heappop(q)
        result = min(result, -td)
        if grid[y][x] == 'J':
            return result
        td *= -1
        for i in range(4):
            ny, nx = y+dy[i], x+dx[i]
            if 0 <= ny < n and 0 <= nx < m and not visited[ny][nx]:
                visited[ny][nx] = True
                heapq.heappush(q, (-trees_dists[ny][nx], ny, nx))
between_tree_and_me()
print(go_to_J())