티스토리 뷰

PS/Codeground

[코드그라운드 연습문제] 두 개의 네비게이션

킹갓제네럴충무공 박트리 2017.08.27 23:12

두 개의 네비게이션


문제


그래프가 주어지고 1번 회사에서 N번 집까지 가는동안 경보음을 최소로 듣는 경우를 구하는 것이다.



문제 풀이


먼저 출발지인 회사에서 집으로 가는 경로 들은 여러곳이 있을 것이다.

dist[x] 를 x에서 부터 n까지 가는 최단거리라고 정의하자.

그렇다면 현재 위치 u와 연결된 v들에 대해서 

dist[v]+w(u,v) == dist[u] 라면 v는 u에서 가는 최단 경로이다.

아니라면 v로 가면 경보음이 울리게 된다. 이와 같은 정리를 이용해서 아이폰과 안드로이드를 사용하였을 때 u->v의 경보음이 울리는지

울리지 않는지 판별하면 된다.

모든 위치 u와 그와 연결된 v에 대해서 위의 값을 구하고 새로운 그래프를 만든후 다시 한번 최단경로 알고리즘을 돌리면 된다.


약간 디테일한 구현 방법으로는 dist[x]를 구하기 위해서는 모든 일방통행 간선을 반대로 넣고 n번 위치에서 출발하는 다익스트라를 돌리면 모든 dist[x]를 쉽게 구할수 있다.

이러한 방법으로 안드로이드, 아이폰에서 dist[x]를 구하고 dfs를 n번 위치 부터 출발하면서 모든 엣지에 대해서 경보음 수를 저장하면 된다.

 

소스 코드

코드 보기


댓글
댓글쓰기 폼