문제 링크 : https://www.acmicpc.net/problem/1854 이 문제는 시작 정점부터 각각의 정점까지의 최단 거리를 찾는 다익스트라 알고리즘을 변형한 문제이다.단순히 최단 거리가 아닌 k번째 최단 경로를 구해야 한다.일반적으로 다익스트라 알고리즘은 각 정점까지 최단거리만을 저장하는 배열을 가지고 있는데이 문제를 해결하기 위해서는 각 정점까지의 거리 중 k번째로 짧은 거리까지 저장할 수 있는 자료구조가 필요하다. 여기서 PriorityQueue를 사용하면 매번 따로 처리해주지 않아도편하게 k번째 최단거리를 구할 수 있다. 일반적인 다익스트라 알고리즘 문제에서는 인접 리스트를 구현해서 푸는 것이 더 편하지만이 문제를 해결하기 위해서는 이런 인접 행렬을 이용해야 한다.arr[1][2] = ..

문제 링크 : https://www.acmicpc.net/problem/1753 이 문제는 다익스트라 알고리즘을 사용할 줄 아는지 묻는 문제이다.따라서 다익스트라 알고리즘을 코드로 구현만 해주면 된다. 간단하게 다익스트라 알고리즘을 알아보자. 만약 위와 같은 모양의 그래프가 있다고 가정해 보자.그래프 문제에서 가중치가 있는 간선을 다룰 때는 인접 리스트를 표현할 때클래스를 하나 생성하여 다음 정점과 해당 정점까지의 거리를 표현할 수 있다. 인접 리스트로 가중치가 있는 그래프를 표현한다면위와 같이 표현할 수 있을 것이다. 이제 다익스트라 알고리즘을 시작하기 전에시작 정점에서 각각의 정점까지의 거리를 나타내는 dist 배열과PriorityQueue인 pq를 초기화한다.이때 (정점, 시작정점부터 해당 정점까지..

문제 링크 : https://www.acmicpc.net/problem/1948 이 문제는 2가지를 구해야 하는 문제이다.첫 번째는 단순 위상정렬을 통해 도착지점까지 가장 오래 걸리는 경우가 몇인지를 구하면 되기 때문에비교적 간단하다. 두 번째가 이 문제의 핵심인데 가장 먼 거리를 이동하는 루트에 있는 도로의 개수를 구하는 문제이다.이것은 역방향 인접 그래프를 통해 해결할 수 있다. 우선 가장 기본이 되는 정방향 인접그래프를 구현한다.이때 노드와 노드 사이의 거리도 구해야 하기 때문에 새로운 클래스인Node 클래스를 만들어 목표 노드와 해당 노드까지의 거리를 나타내고이를 2차원 리스트에 저장하면 된다. 위의 정방향 인접 그래프를 위상정렬 알고리즘을 통해 구하면 위와 같이 2번 노드부터 7번 노드까지 임계..

문제 링크 : https://www.acmicpc.net/problem/1516 이 문제는 어떤 건물을 짓기 위해 먼저 지어야 하는 건물이 있을 수 있다는 문장에 주목해야 한다.여기서 각 건물을 노드라고 생각한다면 그래프 형태에서 노드의 순서를 정렬하는위상 정렬 알고리즘을 사용하는 문제라는 것을 알 수 있기 때문이다. 이때 위상정렬 알고리즘을 실행하면서 각 건물을 짓는데 필요한 총 시간을 업데이트해줘야 하는데여기서는 Math.max(현재 건물에 저장된 총 시간, 이전 건물에 저장된 총 시간 + 현재 건물을 짓는데 들어가는 시간)으로 계산해주면 된다. 건물을 노드라고 봤을 때진입 차수 배열, 건물별 생산 시간, 건물 하나에 들어가는 총 시간등을 저장하는 배열이 별도로 필요하다.package boj;impo..