Baekjoon 18352 특정 거리의 도시 찾기 JAVA

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

18352번: 특정 거리의 도시 찾기

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

GitHub - JUNGSOONIL/JAVA: JAVA 소스 코드

해당 문제는 도시간의 단방향 연결 정보가 추어졌을때 어느 시작 도시에서 특정 거리만큼 이동해서 갈수있는

도시의 목록을 구하는 문제다. 가능한 도시가 없을 경우 -1 출력

 

해당 문제는 다익스트라를 이용해서 해결했으며, 도시간의 가중치는 1로 두어서 해결했다.

 

입력처리를하면서 이동 거리를 저장할 배열을 max값으로 초기화 해주고 ArrayList를 배열로 사용하여

연결 정보를 저장하고 PriorityQueue는 람다식으로 정렬하여주었다.

 

이후 pq에 출발지와 거리0 을넣어준뒤 다익스트라를 실시하여준다.

방문 체크를 하고 현재 위치값 + 1에서 가고자하는 위치의 값을 비교하는데 가고자 하는

값이 클경우 현재값 +1로 바꿔주고 pq에 추가해준다.

 

이후 cost배열을 통해 원하는 거리만큼 있는 도시를 체크하는데 이때 시작점은 제외시켜 줘야한다.

나는 StringBuilder를 이용해서 체크해주었는데 만약 해당하는 도시가 있으면 sb에 넣어주고

이후 sb가 비었다면 해당하는 도시가 없으니 -1을 sb가 비어있지 않다면 도시가 있으므로

sb를 출력해 주었다.