Baekjoon 14496 그대, 그머가 되어 JAVA

https://www.acmicpc.net/problem/14496

14496번: 그대, 그머가 되어

https://github.com/JUNGSOONIL/JAVA/blob/main/BAEKJOON%2014496

GitHub - JUNGSOONIL/JAVA: JAVA 소스 코드

해당 문제는 그냥 그래프가 주어졌을 때 시작 정점부터 도착 정점까지 가는

최소 치환 횟수를 구하는 문제다.

​

bfs를 이용해서 해결 가능할 거라 생각했는데,

예전에 배웠던 다익스트라 알고리즘을 다시 깨우치고자

다익스트라 알고리즘을 이용했다.

​

먼저 그래프에 연결정보에 대해서는 ArrayList를 배열 형식으로 사용했으며,

2번 테케에서 양방향 그래프인 걸 확인할 수 있다.

​

PriorityQueue에 시작 정점과 0(치환 횟수)을 넣어준 뒤, pq가 빌 때까지

반복을 하면서 해당 정점에 해당하는 연결된 간선들을 리스트에서

가져와서 방문 안 했으면 방문 처리해 주면서 치환 횟수를 1 늘려 pq에 삽입해 주고

반복하게 되며 만약 도착하면 기저 조건에 의해 결괏값이 갱신될 것이고

그렇지 않으면 결괏값은 초깃값 그대로이기 때문에 해당 값을

통해 결과를 출력해 주면 된다.