나아가는중

백준 Baekjoon 1238번 파티 - JAVA 문제 풀이 다익스트라 알고리즘을 사용하여 푸는 문제이다. 주로 양방향 그래프가 주어지고 다익스트라 알고리즘을 활용하여 푸는 문제들이 나왔는데, 이번에는 단방향 그래프가 주어졌다. 모든 마을에서 다익스트라를 사용하여 최단거리를 구하는 방법도 존재하지만, X를 출발지로 지정하면 다익스트라 알고리즘을 두번만 사용하여 구할 수 있다. 정방향과 역방향 그래프와 각각의 최단 거리를 저장할 배열이 필요하다. 주어진 단방향 그래프를 그대로 입력받고 다익스트라를 사용하면 모든 마을에서 X까지의 최단거리를 구할 수 있다. 하지만 반대로 X에서 마을로 돌아오는 길을 구하기 위해서는 입력 받는 그래프를 역으로 바꿔 저장한 다음 다익스트라를 사용하여 구해야 한다. 소스 코드 i..

백준 Baekjoon 5972번 택배 배송 - JAVA 문제 풀이 다익스트라 알고리즘 문제이다. 1번 헛간에서 N번 헛간까지 가는 최소한의 소들을 만나며 지나가는 비용을 찾아 출력하면 된다. 여러 방법으로 다익스트라를 구현할 수 있는데 연결리스트 배열과 우선순위 큐를 사용하여 풀었다. 헛간간에 무방향이기 때문에 양방향으로 헛간의 정보를 입력 받는다. 모든 방법을 탐색하는 것이 아닌 우선순위 큐를 사용하여 시간 복잡도를 줄였다. 시작점인 1번 헛간 이외의 헛간은 최대길이로 초기화 하고 이를 비교하며 최소 비용을 갱신하는 방법을 사용하였다. 현재 비용과 새로운 비용을 비교하여 해당 헛간으로 가는 비용이 더 적은 경우에만 큐에 추가하는 방식이다. boolean배열을 만들어 이미 방문한 헛간은 다시 방문하지 않..