문제내용
https://www.acmicpc.net/problem/1238
1238번: 파티
첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어
www.acmicpc.net
N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다.
어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다.
각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다.
이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다. N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은 누구일지 구하여라.
입력
첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어온다. 시작점과 끝점이 같은 도로는 없으며, 시작점과 한 도시 A에서 다른 도시 B로 가는 도로의 개수는 최대 1개이다.
모든 학생들은 집에서 X에 갈수 있고, X에서 집으로 돌아올 수 있는 데이터만 입력으로 주어진다.
출력
첫 번째 줄에 N명의 학생들 중 오고 가는데 가장 오래 걸리는 학생의 소요시간을 출력한다.
문제 접근 방법
이전에 풀었던 다익스트라로 로직을 짜면 되는 문제이다.
문제를 요약해보자면 1~n번학생이 각자의 집에서 x학생 집까지 가는 최단경로와 x학생집에서 각자 집으로 가는 최단경로를 합친 값을 구하고 그중에서 최댓값을 구하면된다.
즉, "'1~n정점에서 x정점으로 최단거리 + x정점에서 1~n정점까지 최단거리 값' 중 최댓값" 이라는 말이다.
로직을 간단히 말하면 아래와 같다.
- 정점과 간선의 가중치를 저장할 리스트 선언
단방향으로 이어진 간선을 표시하기 위해 정점 두개와 간선의 가중치를 저장 해줄 인접리스트를 생성해준다.
이때 제네릭의 경우 정점하나와 간선의 가중치를 나타낼수 있는 객체로 선언해준다.
static ArrayList<ArrayList<Node1238>> list = new ArrayList<ArrayList<Node1238>>();//정점과 간선가중치 리스트 static class Node1238{//정점 하나와 간선의 가중치 int v; int c; public Node1238(int v, int c) { this.v = v; this.c = c; } }
for(int i=0; i<=n; i++)//1~n정점 추가 list.add(new ArrayList<Node1238>()); for(int i=0; i<m; i++) { st = new StringTokenizer(br.readLine()); int v1 = Integer.parseInt(st.nextToken()); int v2 = Integer.parseInt(st.nextToken()); int cost = Integer.parseInt(st.nextToken()); //v1 정점과 연결된 v2정점과 간선 가중치 추가(단방향) list.get(v1).add(new Node1238(v2, cost)); } - goParty(i) 메서드
시작정점부터 1~n번 정점 까지 최단경로를 저장해주는 dp배열을 선해주고
시작정점부터 x정점까지가는 최단경로를 계산해준다.
그리고 dp[x]의 값을 반환해 준다.
//집에서 파티장으로가는 최단경로, 매개변수: 시작정점 public static int goParty(int start) { int[] dp = new int[n+1];//1~n번정점의 최단경로 저장해줄 배열 Arrays.fill(dp, Integer.MAX_VALUE); //가중치를 기준으로 오름차순 정렬 PriorityQueue<Node1238> pq = new PriorityQueue<Node1238>(new Comparator<Node1238>() { @Override public int compare(Node1238 o1, Node1238 o2) { int c1 = o1.c; int c2 = o2.c; if(c1<c2) return -1; else if(c1>c2) return 1; else return 0; } }); dp[start] = 0;//시작은 0으로 초기화 pq.add(new Node1238(start, 0));//시작정점 추가 while(!pq.isEmpty()) { Node1238 cur = pq.poll();//현재 정점 뽑기 //현재정점의 최단경로 값보다 이전정점에서 현재정점으로 오는 최단경로 값이 더 크면 갱신 안함 if(dp[cur.v] < cur.c) continue; if(cur.v==x) break; //현재 정점이 목표정점일때 중단 //현재 정점으로 부터 인접노드를 탐색 for(int i=0; i<list.get(cur.v).size(); i++) { Node1238 next = list.get(cur.v).get(i); //"인접노드의 최단경로 값 > 현재정점까지 값 + 인접노드 정점까지 가중치 값" 이면 // 갱신할 필요가 최단경로 값을 더 작은값으로 갱신할 필요가 있음. if(dp[next.v] > cur.c + next.c) { dp[next.v] = cur.c + next.c;//인접노드의 최단경로 갱신 pq.add(new Node1238(next.v, dp[next.v]));//갱신한 노드 추가 } } } return dp[x];//목표정점일때 최단경로 값 반환 } - goHome(i) 메서드
goParty메서드와 같은 원리이다.
다만 반환값의 경우 x정점(시작정점)부터 각자의 집을 나타내는 정점인 1~n번정점 까지 최단경로를 반환해준다.
//goParty 메서드와 원리 같음.(파티장에서 집으로 돌아오는 최단경로) //매개변수 : 끝나는 정점 public static int goHome(int endV) { int[] dp = new int[n+1]; Arrays.fill(dp, Integer.MAX_VALUE); PriorityQueue<Node1238> pq = new PriorityQueue<Node1238>(new Comparator<Node1238>() { @Override public int compare(Node1238 o1, Node1238 o2) { int c1 = o1.c; int c2 = o2.c; if(c1<c2) return -1; else if(c1>c2) return 1; else return 0; } }); dp[x] = 0; pq.add(new Node1238(x, 0)); while(!pq.isEmpty()) { Node1238 cur = pq.poll(); if(dp[cur.v] < cur.c) continue; if(cur.v==endV) break; for(int i=0; i<list.get(cur.v).size(); i++) { Node1238 next = list.get(cur.v).get(i); if(dp[next.v] > cur.c + next.c) { dp[next.v] = cur.c + next.c; pq.add(new Node1238(next.v, dp[next.v])); } } } return dp[endV]; } - 최댓값 찾기
1~n번 정점이 x정점 까지 갔다가 다시 돌아오는 경로를 합친 값중 최댓값을 찾는다.
//1~n번 정점으로부터 x정점까지 왔다갔다 거리재기 for(int i=1; i<=n; i++) { if(i==x) continue;//목표 정점일때는 어차피 0임(제외) answer = Math.max(answer, goParty(i)+goHome(i));//최댓값 }
다익스트라 알고리즘을 잘모르겠다면 아래 문제를 먼저 풀어보고 오자.
https://record-developer.tistory.com/89
[JAVA] BOJ(백준) - 최단경로 - 1753
문제내용 https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다..
record-developer.tistory.com
풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class Main {
static int n, m, x; //정점 개수, 간선 개수, 시작(끝)정점
static ArrayList<ArrayList<Node1238>> list = new ArrayList<ArrayList<Node1238>>();//정점과 간선가중치 리스트
static class Node1238{//정점 하나와 간선의 가중치
int v;
int c;
public Node1238(int v, int c) {
this.v = v;
this.c = c;
}
}
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int answer = Integer.MIN_VALUE;//정답 변수
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
x = Integer.parseInt(st.nextToken());
for(int i=0; i<=n; i++)//1~n정점 추가
list.add(new ArrayList<Node1238>());
for(int i=0; i<m; i++) {
st = new StringTokenizer(br.readLine());
int v1 = Integer.parseInt(st.nextToken());
int v2 = Integer.parseInt(st.nextToken());
int cost = Integer.parseInt(st.nextToken());
//v1 정점과 연결된 v2정점과 간선 가중치 추가(단방향)
list.get(v1).add(new Node1238(v2, cost));
}
//1~n번 정점으로부터 x정점까지 왔다갔다 거리재기
for(int i=1; i<=n; i++) {
if(i==x) continue;//목표 정점일때는 어차피 0임(제외)
answer = Math.max(answer, goParty(i)+goHome(i));//최댓값
}
System.out.println(answer);//출력
}
//집에서 파티장으로가는 최단경로, 매개변수: 시작정점
public static int goParty(int start) {
int[] dp = new int[n+1];//1~n번정점의 최단경로 저장해줄 배열
Arrays.fill(dp, Integer.MAX_VALUE);
//가중치를 기준으로 오름차순 정렬
PriorityQueue<Node1238> pq = new PriorityQueue<Node1238>(new Comparator<Node1238>() {
@Override
public int compare(Node1238 o1, Node1238 o2) {
int c1 = o1.c;
int c2 = o2.c;
if(c1<c2) return -1;
else if(c1>c2) return 1;
else return 0;
}
});
dp[start] = 0;//시작은 0으로 초기화
pq.add(new Node1238(start, 0));//시작정점 추가
while(!pq.isEmpty()) {
Node1238 cur = pq.poll();//현재 정점 뽑기
//현재정점의 최단경로 값보다 이전정점에서 현재정점으로 오는 최단경로 값이 더 크면 갱신 안함
if(dp[cur.v] < cur.c) continue;
if(cur.v==x) break; //현재 정점이 목표정점일때 중단
//현재 정점으로 부터 인접노드를 탐색
for(int i=0; i<list.get(cur.v).size(); i++) {
Node1238 next = list.get(cur.v).get(i);
//"인접노드의 최단경로 값 > 현재정점까지 값 + 인접노드 정점까지 가중치 값" 이면
// 갱신할 필요가 최단경로 값을 더 작은값으로 갱신할 필요가 있음.
if(dp[next.v] > cur.c + next.c) {
dp[next.v] = cur.c + next.c;//인접노드의 최단경로 갱신
pq.add(new Node1238(next.v, dp[next.v]));//갱신한 노드 추가
}
}
}
return dp[x];//목표정점일때 최단경로 값 반환
}
//goParty 메서드와 원리 같음.(파티장에서 집으로 돌아오는 최단경로)
//매개변수 : 끝나는 정점
public static int goHome(int endV) {
int[] dp = new int[n+1];
Arrays.fill(dp, Integer.MAX_VALUE);
PriorityQueue<Node1238> pq = new PriorityQueue<Node1238>(new Comparator<Node1238>() {
@Override
public int compare(Node1238 o1, Node1238 o2) {
int c1 = o1.c;
int c2 = o2.c;
if(c1<c2) return -1;
else if(c1>c2) return 1;
else return 0;
}
});
dp[x] = 0;
pq.add(new Node1238(x, 0));
while(!pq.isEmpty()) {
Node1238 cur = pq.poll();
if(dp[cur.v] < cur.c) continue;
if(cur.v==endV) break;
for(int i=0; i<list.get(cur.v).size(); i++) {
Node1238 next = list.get(cur.v).get(i);
if(dp[next.v] > cur.c + next.c) {
dp[next.v] = cur.c + next.c;
pq.add(new Node1238(next.v, dp[next.v]));
}
}
}
return dp[endV];
}
}마치며
위에 링크해놓은 최단경로 문제를 풀수 있다면 충분히 풀 수 있는 문제라고 생각한다.
'알고리즘 > BOJ' 카테고리의 다른 글
| [JAVA] BOJ(백준) - 가르침 - 1062 (0) | 2022.02.15 |
|---|---|
| [JAVA] BOJ(백준) - ACM Craft - 1005 (0) | 2022.02.10 |
| [JAVA] BOJ(백준) - 빗물 -14719 (0) | 2022.02.06 |
| [JAVA] BOJ(백준) - 네트워크 연결 - 1922 (0) | 2022.02.02 |
| [JAVA] BOJ(백준) - 최단경로 - 1753 (0) | 2022.02.02 |
