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

문제

출처 : www.acmicpc.net/problem/2917

2917번: 늑대 사냥꾼

늑대 현우는 사냥꾼을 피해서 최대한 안전한 경로로 집으로 도착해야한다.

사냥꾼은 나무뒤에 숨어있다.

 

N*M 배열이 주어지고,

나무의 위치는 +, 현우의 위치는 V, 오두막의 위치는 J로 주어진다.

 

현우의 위치에서 집까지 가는 가장 안전한 경로에서 나무와 현우의 거리의 최솟값을 출력하는 문제다.

풀이

 

BFS를 돌려서 나무와 모든정점들에 최단거리를 저장해주고, 현우의 위치를 기준으로 다익을 돌려 가장 안전한 길에서, 나무와의 거리가 최솟값인곳을 찾아주면된다.

 

우선, 나무의 위치를 시작지점으로 BFS를돌려서 나무를 제외한 모든정점까지의 최단거리를 저장해준다. 그러면, 나무의 위치에서 각 정점까지 도달하는데 걸리는 최단거리가 저장된다.

 

예제 1

+ . . . 

 . . . . 

 . . . . 

V . . J

의 경우 BFS로 최단경로를 저장해주면

0 1 2 3 

1 2 3 4 

2 3 4 5

3 4 5 6

이 저장된다.

 

이때, 현우의 위치를 기준으로 다익을 돌려주는데, 이때 프라이어리티 큐를 사용해서 최댓값을 팝한다.

문제를 읽어보면, 현우는 집까지 가는 가장 안전한 길을 선택하는데, 현우의 현재 위치에서 나무와의 거리가 가장 먼 지점을 선택해서 이동해야만 안전한길이기 때문에 프라이어리티 큐를 사용한다.

항상 최댓값을 찾아 다익을 돌리면 가장 먼저 집에 도착했을때 선택한 경로들이 가장 안전한길이다. 이때, 최솟값인 곳을 찾아 저장하고 집에 도착했을때 저장한 최솟값을 출력하고 종료하면 된다.

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/2917%20%EB%8A%91%EB%8C%80%20%EC%82%AC%EB%83%A5%EA%BE%BC/main.cpp

devxb/JJUNalgo