분류가 다익스트라로 돼있어서 의문이 들었었다.
BFS 또는 DFS 면 되지 않을까??
질문 게시판을 가보니 BFS & Prirority queue 를 이용해서 최단거리를 구하는 것은 다익스트라다!
질문 게시판에서 솔루션은 얻었는데, 아이디어를 모르겠었다.
그래서 검색을 좀 하니까 바로 아이디어를 얻었다.
1. 도착지점에 도착할때, 가장 작은 가중치를 출력하라.
가장 작은 가중치를 출력할 때, Prioritiy queue 를 이용한다.
weight 를 기준으로 Priority queue 를 구성
2. 그러면 도착한 순간이 가장 작은 가중치를 갖게된다.
끝.
'IT > 알고리즘' 카테고리의 다른 글
| BOJ 백준온라인져지 14502 연구소 풀이 (0) | 2018.01.14 |
|---|---|
| BOJ 백준온라인져지 4485 녹색 옷 입은 애가 젤다지? 풀이 (0) | 2018.01.13 |
| BOJ 백준온라인져지 1504 특정한 최단 경로 풀이 (0) | 2018.01.09 |
| BOJ 백준온라인져지 1918 후위표기식 풀이 (0) | 2018.01.07 |
| BOJ 백준온라인져지 1655 가운데를 말해요 풀이 (0) | 2018.01.06 |