주의사항
- JAVA를 사용하여 프로그램을 사용하였습니다.
- 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.
public class Main{
public static void main(String[] args){
}
}문제 설명
접근 방법
최단경로는 시작 정점에서 목표 정점까지 최소의 비용으로 갈 수 있는 경로를 구하는 것입니다.
최단 경로를 구하는 알고리즘은 대표적으로 3개가 존재합니다.
1. 다익스트라 알고리즘
2. 벨만-포드 알고리즘
3. 플로이드 워셜 알고리즘
3가지 알고리즘은 문제를 해결할 때 사용하는 알고리즘만 설명하도록 하겠습니다.
다익스트라 알고리즘이란?
1. 출발 정점에서 인접한 정점으로 이동합니다.
2. 인접한 정점에서 가장 적은 가중치(거리)의 정점을 먼저 탐색합니다.
3. 이동을 할 때마다 이동한 거리가 현재 저장된 거리보다 작으면 변경합니다.
4. 위 과정을 반복이 끝나면 출발 정점에서 각 정점에 도착하는 최소 거리을 구할 수 있습니다.
글로는 잘 설명하지 못한 것 같아서 아래에 예제 문제를 풀면서 어떻게 진행되는지 자세히 보여드리겠습니다.
더 자세한 내용은 아래 링크를 통해 확인해주시기 바랍니다.
데이크스트라 알고리즘 - 위키백과, 우리 모두의 백과사전
컴퓨터 과학에서, 데이크스트라 알고리즘(영어: Dijkstra algorithm) 또는 다익스트라 알고리즘은 도로 교통망 같은 곳에서 나타날 수 있는 그래프에서 꼭짓점 간의 최단 경로를 찾는 알고리즘이다.
ko.wikipedia.org
이 문제에 핵심은
1. 입력값으로 주는 내용은 모두 그래프의 내용입니다.
2. 시작점에서 g와 h를 지나는 교차로를 지나야 한다.
3. g와 h를 지났으며 목적지 후보에 최단 거리이면 목적지를 오름차순으로 출력한다.
4. g와 h를 지났으나 최단 거리가 아닌 목적지는 출력하지 않으며 모두 아닌 경우 -1를 출력한다.
5. 방향성이 없는 그래프가 주어진다. = 방향이 없는 양방향 간선이다.
저는 BFS(너비우선탐색)와 다익스트라 알고리즘을 사용하여 해결하였습니다.
그래프에 대한 내용을 정의하기 위해 ArrayList<ArrayList<Integer>>의 형태로 리스트를 만들어주었습니다.
위와 같이 정의하여 데이터를 저장하면 각 정점이 어떤 정점으로 이동하는지 간단하게 저장할 수 있습니다.
예를 들어
1 -> 4
1 -> 3
2 -> 5
3 -> 4
ArrayList<ArrayList<Integer>>의 저장되는 모습은 리스트 안에 리스트가 포함되는 형식으로 저장됩니다.
| 정점 | ||
| 1 | 3 | 4 |
| 2 | 5 | |
| 3 | 1 | 4 |
| 4 | 1 | 4 |
| 5 | 2 |
그래프의 값을 리스트에 저장하였다면 각 정점을 기준으로 BFS탐색으로 다익스트라 알고리즘을 구현하였습니다.
정점 1에서 g와 h의 교차로를 지나서 N까지 가는 방법은
1 -> g -> h -> N
1 -> h -> g -> N
이 두 가지 방법과 g와 h의 교차로를 지나지 않고 N까지 가는 1 -> N의 최단 경로를 구해서 비교합니다.
만약 g와 h의 교차로 지났을 때 최단 거리가 지나지 않을 때와 같다면 해당 경로는 최단 경로입니다.
하지만 최단 거리와 같지 않고 크다면 해당 경로는 최단 경로가 아니므로 목적지에 해당하지 않습니다.
만약 N = 7, g = 2, h = 5이면
1 -> g까지 가는 최단 거리
g -> h까지 가는 최단 거리
h -> N까지 가는 최단 거리
모두 더하면 1 -> g -> h -> N까지 가는 최단 경로를 구할 수 있습니다.
1 -> h까지 가는 최단 거리
h -> g까지 가는 최단 거리
g -> N까지 가는 최단 거리
모두 더하면 1-> h -> g -> N까지 가는 최단 경로를 구할 수 있습니다.
이후 두 경우의 최단 경로와 1 -> N의 최단 경로를 비교하여 같은 경로의 목적지를 출력합니다.
예제 입력1에서 첫 번째 테스트케이스의 그래프를 표로 확인하며 보여드리겠습니다.
아래는 예제로 주어진 그래프입니다.
그래프의 내용이 저장된 ArrayList<ArrayList<>>의 해당하는 표
| 정점 | |||
| 1 | 2(거리 : 6) | ||
| 2 | 3(거리 : 2) | ||
| 3 | 2(거리 : 2) | 4(거리 : 4) | 5(거리 : 3) |
| 4 | 3(거리 : 4) | ||
| 5 | 3(거리 : 3) |
최단 경로를 구해야 하는 경우는
1->g, g->h, h->N의 3가지 경우
1->h, h->g, g->N의 3가지 경우
1 -> N의 경우
BFS를 진행하는 과정은 1->g을 구하는 과정만 보여줄 것입니다.
출발 정점1에서 각 지점의 최소 거리을 정리한 표(자신 거리는 = 0, 아직 가보지 않은 곳은 INF(무한대)로 표현)
| 1 | 2 | 3 | 4 | 5 |
| 0 | INF | INF | INF | INF |
1. 출발 정점 1에서 인접한 정점으로 이동합니다.
정점 2로 이동합니다.
| 1 | 2 | 3 | 4 | 5 |
| 0 | 6 | INF | INF | INF |
원래 표의 정점 2의 거리는 INF로써
6 < INF이므로 INF가 6으로 변경되었습니다.
2. 간선에 거리가 적었던 정점 2에서 인접한 정점을 탐색합니다.
정점 3으로 이동합니다.
| 1 | 2 | 3 | 4 | 5 |
| 0 | 6 | 8 | INF | INF |
현재 정점의 거리 : 6, 간선의 거리 : 2 = 6 + 2 = 8
원래 표의 정점 3의 거리는 INF로써
8 < INF이므로 INF가 8으로 변경되었습니다.
3. 정점 2의 인접하여 거리가 적은 정점 3을 탐색합니다.
정점 4로 이동합니다.
| 1 | 2 | 3 | 4 | 5 |
| 0 | 6 | 8 | 12 | INF |
현재 정점의 거리 : 8, 간선의 거리 : 4 = 8 + 4 = 12
원래 표의 정점 4의 거리는 INF로써
12 < INF이므로 INF가 12으로 변경되었습니다.
정점 5로 이동합니다.
| 1 | 2 | 3 | 4 | 5 |
| 0 | 6 | 8 | 12 | 11 |
현재 정점의 거리 : 8, 간선의 거리 : 3 = 8 + 3 = 11
원래 표의 정점 5의 거리는 INF로써
11 < INF이므로 INF가 11으로 변경되었습니다.
4. 더 이상 탐색할 수 있는 간선이 존재하지 않기 때문에 탐색을 종료합니다!
현재 최소 거리가 저장된 표를 순서대로 결과로 출력합니다.
| 1 | 2 | 3 | 4 | 5 |
| 0 | 6 | 8 | 12 | 11 |
g = 2, h = 3, N(목적지 후보) : 5, 4이고 구해야하는 최단 경로를 모두 구하면
목적지 후보가 5일 때
1 -> g(2) = {0, 6, 8, 12, 11} = 1에서 2으로 가는 최단경로 = 6
g(2) -> h(3) = {6, 0, 2, 6, 5} = 2에서 3으로 가는 최단경로 = 2
h(3) -> N(5) = {8, 2, 0, 4, 3} = 3에서 5으로 가는 최단경로 = 3
1 -> h(3) = {0, 6, 8, 12, 11} = 1에서 3으로 가는 최단경로 = 8
h(3) -> g(2) = {8, 2, 0, 4, 3} = 3에서 2으로 가는 최단경로 = 2
g(2) -> N(5) = {6, 0, 2, 4, 3} = 2에서 5으로 가는 최단경로 = 3
1-> N(5) = {0, 6, 8, 12, 11} = 1에서 5으로 가는 최단경로 = 11
1 -> g -> h -> N = 6 + 2 + 3 = 11
1 -> h -> g -> N = 8 + 2 + 3 = 13
1 -> N으로 가는 경우와 1 -> g -> h -> N의 경우가 11로 동일하기 때문에
g와 h를 지나서 목적지 5로 가는 것이 최단 경로이기 때문에 목적지 5는 결과로 출력이 가능하다.
위 방법을 반복하여 구하면 됩니다.
※ 저는 g -> h, h -> g를 가는 다익스트라 알고리즘을 이용하여 구하지 않고 양방향 그래프이기 때문에
그래프의 값을 입력받을 때 g와 h의 교차로 가중치를 따로 저장하였다가 더하는 형식으로 구현하였습니다.
문제를 해결한 알고리즘의 과정입니다.
1. 그래프에 대한 정보를 ArrayList<ArrayList<node>>에 저장합니다.
2. 1 -> g -> h -> N, 1 -> h -> g -> N, 1 -> N 경우를 다익스트라로 탐색합니다.
3. g와 h를 지나는 경로와 1 -> N의 최단 경로와 동일하면 목적지로 확인하여 결과로 출력합니다.
- BufferedReader를 사용하여 입력 값을 받았습니다.
- StringTokenizer를 통해 그래프에 대한 정보를 저장하였습니다.
- 그래프에 사용할 point(정점), cost(거리)를 저장하는 node 생성자를 만들었습니다.
- 그래프에 내용 저장할 ArrayList<ArrayList<Integer>> graph를 만들었습니다.
- BFS로 최단 경로(다익스트라)를 구하는 unconfirmedGoal함수를 만들었습니다.
- 위에서 설명한 세 가지 경우의 최단 경로를 구하였습니다.
- BufferedWriter에 g와 h를 지나며 최단 경로인 목적지를 오름차순으로 저장하였습니다.
- BufferedWriter에 저장된 결과값을 출력하였습니다.
- unconfirmedGoal은 distance[], graph와 PriorityQueue를 통해 인접한 정점을 탐색하였습니다.
- unconfirmedGoal는 다익스트라 알고리즘과 BFS를 구조를 이용하여 작성하였습니다.
- unconfirmedGoal는 목적지에 대한 최단 거리를 반환하도록 하였습니다.
결과 코드
import java.io.*;
import java.util.*;
public class Main{
//-------큐에 목적지와 가중치 생성자--------
public static class node{
int point, cost;
public node(int point, int cost) {
this.point = point;
this.cost = cost;
}
public int getPoint() {
return point;
}
public int getCost() {
return cost;
}
}
public static int T;
public static int[] goal,distance; //목적지 후보, 최단 거리 저장 배열
public static ArrayList<Integer> result; //목적지 확정 저장 배열
public static ArrayList<ArrayList<node>> graph = new ArrayList<>(); //그래프 값
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//입력값 처리하는 BufferedReader
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
//결과값 출력하는 BufferedWriter
//-----입력값 저장 및 그래프 초기화------
StringTokenizer st;
T = Integer.parseInt(br.readLine());
for(int i=0;i<T;i++) {
st = new StringTokenizer(br.readLine()," ");
int n = Integer.parseInt(st.nextToken()); //정점 개수
int m = Integer.parseInt(st.nextToken()); //간선 개수
int t = Integer.parseInt(st.nextToken()); //목적지 후보 개수
for(int j=0;j<=n;j++) //그래프 초기화
graph.add(new ArrayList<>());
st = new StringTokenizer(br.readLine()," ");
int s = Integer.parseInt(st.nextToken()); //시작 정점
int g = Integer.parseInt(st.nextToken()); //지나는 정점 g
int h = Integer.parseInt(st.nextToken()); //지나는 정점 h
int crossingCost = 0; // g와 h의 교차로 값 저장 변수
for(int j=0;j<m;j++) {
//그래프 값 저장
st = new StringTokenizer(br.readLine()," ");
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int d = Integer.parseInt(st.nextToken());
if((a==g || a==h) && (b==g || b==h))
crossingCost = d; //g와 h의 교차로 값 저장
graph.get(a).add(new node(b,d));
graph.get(b).add(new node(a,d));
}
//목적지 후보 배열 초기화
goal = new int[t];
for(int j=0;j<t;j++)
goal[j] = Integer.parseInt(br.readLine());
distance = new int[n+1];
result = new ArrayList<>();
for(int j=0;j<t;j++) {
int end = goal[j]; //목적지 후보 가져오기
int res1 = unconfirmedGoal(s, end); // 1 -> 목적지 후보 최단 경로
//1 -> g -> h -> N 최단 경로
int res2 = unconfirmedGoal(s, g) + crossingCost;
res2 += unconfirmedGoal(h, end);
if(res1 == res2) {
result.add(end);
continue;
}
//1 -> h -> g -> N 최단 경로
int res3 = unconfirmedGoal(s, h) + crossingCost;
res3 += unconfirmedGoal(g, end);
if(res1 == res3)
result.add(end);
}
Collections.sort(result); //목적지 오름차순 정렬
for(int j=0;j<result.size();j++)
bw.write(result.get(j) + " "); //목적지 BufferedWriter 저장
bw.newLine();
result.clear();
graph.clear();
}
bw.flush(); //결과 출력
bw.close();
br.close();
}
//다익스트라를 이용한 최단 경로 구하는 함수
public static int unconfirmedGoal(int start, int end) {
PriorityQueue<node> queue = new PriorityQueue<node>(new Comparator<node>() {
@Override
/*
우선순위 큐를 사용해서 현재 정점들에서 거리가 가장 적은 정점을
바로 poll()을 할 수 있도록 거리가 작은 순으로 Queue에 저장되도록
Comparator를 설정해주었습니다.
*/
public int compare(node o1, node o2) {
return o1.cost - o2.cost;
}
});
//최단 거리 저장 배열 초기화
Arrays.fill(distance, Integer.MAX_VALUE);
distance[start] = 0;
queue.add(new node(start, 0));
while(!queue.isEmpty()) {
node temp = queue.poll();
int point = temp.getPoint();
int cost = temp.getCost();
/*
정점에 도착했을 때 최소 거리보다 크면
해당 정점에 간선 어디를 가도 최소 거리가 되지 않기 때문에
해당 탐색을 그대로 넘어갔습니다.
*/
if(distance[point] < cost)
continue;
for(node value : graph.get(point)) {
if(distance[value.getPoint()] > cost + value.getCost()) {
//더 작은 경로 찾았을 때
distance[value.getPoint()] = cost + value.getCost();
queue.add(new node(value.getPoint(),distance[value.getPoint()]));
}
}
}
return distance[end];
}
}'백준' 카테고리의 다른 글
| [백준] code.plus(다이나믹 프로그램 part 1,JAVA)15990번, 1, 2, 3 더하기 5 (0) | 2022.04.06 |
|---|---|
| [백준] 단계별로 풀어보기(단계:25, 최단 경로,JAVA)11657번, 타임머신 (0) | 2022.04.05 |
| [백준] code.plus(다이나믹 프로그램 part 1,JAVA)16194번, 카드 구매하기 2 (0) | 2022.04.05 |
| [백준] code.plus(다이나믹 프로그램 part 1,JAVA)11052번, 카드 구매하기 (0) | 2022.04.05 |
| [백준] 단계별로 풀어보기(단계:25, 최단 경로,JAVA)1504번, 특정한 최단 경로 (0) | 2022.04.03 |
댓글