백준 2917 늑대 사냥꾼

www.acmicpc.net/problem/2917

2917번: 늑대 사냥꾼

필자는 다익스트라 알고리즘을 활용하여 풀었으나 사실 BFS와 방문체크를 통해도 해결할 수는 있다. 오히려 속도도 더 빠를 것이다.

일단 필자의 풀이를 보면, BFS를 활용하는 방법도 바로 자연스레 이해될 것이다.

사실 한 정점에서 다른 정점으로 갈때의 비용이 항상 1이기에 BFS를 생각하는 것이 더 자연스럽다.

위와 같이 지도 상에 나무( + )가 배치되어있다고 하자. 각 나무에 cost=0을 두고 BFS나 다익스트라 등을 통해 맵 전체 탐색을 하는 것이다. 

그러면 위의 그림과 같이 숫자가 퍼져나간다. 

이 부분 구현을 위해 맵 전체에 cost값을 매우 큰 값으로 설정해두고 다익스트라를 통해 갱신해가도 되지만, 

방문체크를 하여 방문하지 않은 점에 cost를 기록해가는 BFS방식으로 해도 된다. BFS로 하는 것이 로그(우선순위 큐) 계산이 붙지 않아 더 빠르다. 그림에서 빨강색으로 X 표시된 부분은 비용 업데이트가 되지 않는다는 뜻이다. 다익스트라에서는 새로 들어오는 값이 기존의 값보다 크기 때문에 갱신이 안될 것이고, BFS에서는 이미 방문한 점을 다시 방문하려 하는 것이기에 갱신이 안된다.

 

위의 맵 탐색을 이어가면 아래와 같이 모든 비용이 매겨진다.

그러면 이제 V에서 시작하여  J까지 이동하면서 (빨강색 경로는 예시일 뿐이다. 다른 여러 가지 경로가 있을 수 있다) 비용이 가장 작은 값을 선택하여 답으로 리턴해주면 된다. 

 

이 문제에 대한 풀이를 생각함에 있어, V에서 J로 가는 경로상에 거치는 점에서 모든 나무까지 거리의 파악하는 방법은 뭔가 직관적으로 좋지 않다는 것을 알 수 있다. 그래서 반대로 모든 나무를 전부 큐나 우선순위 큐등에 담아두고, 맵 전체에 최소 비용 값을 미리 다 구해두는 방법을 생각해내는 것이 핵심이라고 할 수 있다. 그리고 그때 항상 최소값이 기록된다. 만약에 추가적으로 가장 가까운 나무가 어떤 것이냐는 질문에 대한 답을 내고자 한다면, 지도 상에 비용을 구하는 과정에서 해당 비용이 어느 나무에서 온 것인지를 기록해두면 될 것이다. 그때는 큐에 pair 등을 활용하여 [비용, 나무번호]등을 기록하면 된다. 

 

조금 더 추상화하면 위의 그림과 같이 이해할 수 있다. 각 나무에서 동심원을 그리며 파동이 전파되고 가장 먼저 도달한 점에 모두 방문체크를 하는 것이다. 어차피 가장 먼저 도착한 값이 최소비용이기 때문이다. 그렇게 모든 맵을 채웠을 때 종료하고, 이제 V에서 J로 이동만 하면 되는 것이다. 그 과정에서 최소비용 중의 최소비용을 찾으면 된다.

 

 

<주요 내용>

BFS, 다익스트라, 우선순위 큐, 방문체크

 

<코드>

import sys
import heapq
si = sys.stdin.readline


def main():
    n, m = [int(e) for e in si().split()]
    dr, dc = [0, 1, 0, -1], [-1, 0, 1, 0]
    big = 500+500+1
    cost = [[big for _ in range(m)]for _ in range(n)]
    treepq, board = [], []
    for i in range(n):
        board.append(si()[:-1])
        for j in range(m):
            if board[i][j] == 'V':
                vr, vc = i, j
            elif board[i][j] == '+':
                cost[i][j] = 0
                heapq.heappush(treepq, (0, (i, j)))

    while treepq:
        curr = heapq.heappop(treepq)
        currcost, cr, cc = curr[0], curr[1][0], curr[1][1]
        for i in range(4):
            nr, nc = cr+dr[i], cc+dc[i]
            if 0 <= nr < n and 0 <= nc < m:
                if cost[nr][nc] > 1+currcost:
                    cost[nr][nc] = 1+currcost
                    heapq.heappush(treepq, (cost[nr][nc], (nr, nc)))

    pq, mn = [], cost[vr][vc]
    heapq.heappush(pq, (-cost[vr][vc], (vr, vc)))
    visited = [[False for _ in range(m)]for _ in range(n)]
    while pq:
        curr = heapq.heappop(pq)
        currcost, cr, cc = -curr[0], curr[1][0], curr[1][1]
        if visited[cr][cc]:
            continue
        visited[cr][cc] = True
        mn = min(mn, currcost)
        if board[cr][cc] == 'J':
            break
        for i in range(4):
            nr, nc = cr+dr[i], cc+dc[i]
            # if 0 <= nr < n and 0 <= nc < m:
            if 0 <= nr < n and 0 <= nc < m and not visited[nr][nc]:
                heapq.heappush(pq, (-cost[nr][nc], (nr, nc)))

    print(mn)


if __name__ == '__main__':
    main()