[백준 / BOJ] 17835 면접보는 승범이네

문제

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

17835번: 면접보는 승범이네

N개의 도시와 도시에따른 M개의 길, K개의 면접장이 주어진다. 

승범이네라는 회사에서 신입사원을 뽑을려한다.

N개의 도시에 살고있는 면접 준비자들은 자신의 도시에서 가장 가까운 면접장으로 가야한다.

이때 면접장 까지의 거리가 가장 먼 도시와 그때의 거리를 출력하는 문제다.

(만약 거리가 가장 먼 도시가 여러군데라면 번호가 작은 도시를 출력하면된다.)

 

풀이

기본적인 다익스트라로 풀리는 문제였다.

 

도시에서 면접장까지의 거리 = 면접장에서 도시까지의 거리

라고 생각해서 면접장을 시작지점으로해서 다익스트라를 돌렸다. 

 

면접장을 기준으로 다익을 돌리기위해서, K번 면접장의 위치를 입력받을때마다 큐에 {0 , 면접장 인덱스}를 저장해준다. 

(큐에는 {면접장에서 지금까지 이동한 거리, 지금 인덱스}와 같이 저장해줬다.)

 

큐에 저장된 값을 pop해주면서 탐색한다.

면접장에서 지금까지 이동한거리 + 현재 idx에서 다음 idx와 연결된 거리 < 다음 idx에 저장된 거리

가 성립하면 que에 {면접장에서 지금까지 이동한거리 + 현재 idx에서 다음 idx와 연결된 거리, 다음 idx}를 저장해준다.

 

다익스트라를 수행하고 모든정점을 탐색하면서 면접장이 아니면서 거리가 가장 먼 정점을 찾아주면된다.

 

 

다익스트라를 돌릴때 최소힙을 사용하면 시간을 줄일수있다고 알았는데 최소힙을 잘못사용했는지 일반 queue로 했을때 메모리와 시간 둘다 적게걸렸다...

소스코드

https://github.com/devxb/JJUNalgo/blob/master/17835%20%EB%A9%B4%EC%A0%91%EB%B3%B4%EB%8A%94%20%EC%8A%B9%EB%B2%94%EC%9D%B4%EB%84%A4/main.cpp

devxb/JJUNalgo