1. 문제
https://www.acmicpc.net/problem/1238
2. 문제 설명
이 문제는 N개 숫자로 구분된 각각의 마을이 존재하며, 각 마을에는 한 명의 학생이 살고있다.
각 마을을 이어주는 시간이 T만큼 걸리는 단방향 도로가 존재한다.
학생들은 파티를 위해 X마을로 모여서 파티하고 끝나며 다시 자기가 살던 마을로 돌아간다.
이 때 각 학생들은 최단 시간을 통해서만 이동한다.
여기서 가장 시간이 오래걸린 학생의 걸린 시간을 출력하는 문제이다.
이 문제는 다익스트라 알고리즘을 통해서 해결할 수 있다.
다익스트라를 풀어본 적이 없다면, 아래 문제를 먼저 풀어보는 것을 추천한다.
https://soonmin.tistory.com/179
[백준] 1753. 최단경로 - JAVA
1. 문제https://www.acmicpc.net/problem/1753 2. 풀이 과정이 문제는 방향 그래프와 시작점 K가 주어진다. 시작점에서 출발해 다른 모든 정점까지의 최단 경로를 구하는 문제이다.경로가 존재하지 않으면 IN
soonmin.tistory.com
이 문제를 푸는 기본 아이디어는 각 마을 i에서 X까지의 최단 거리 + X에서 i까지의 최단 거리가 i 학생의 왕복 시간이다.
이 중 최댓값을 출력하면 정답으로 처리된다.
처음 풀었던 방식 (비효율적)
모든 마을 i에서 X까지 다익스트라를 N번 실행하여 각각의 i 마을에 대한 최단 거리를 구해주었다.
그리고, X 마을에서 모든 마을까지 다익스트라 1번을 실행하여 최단 거리를 구해주었다.
총 다익스트라를 N + 1번 실행하여 왕복거리를 구했다.
// i 마을 => X
int[] result = new int[N + 1];
for (int i = 1; i <= N; i++) {
int[] dist = dijkstra(i); // i = 출발지점
result[i] = dist[X];
}
// X => i 마을
int[] dist = dijkstra(X); // X = 출발지점
for (int i = 1; i <= N; i++) {
result[i] += dist[i];
}
결과는 성공!!

전체 코드
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
static int N;
static int M;
static int X;
static int INF = 10000 * 100;
static List<List<Point>> graph = new ArrayList<>();
public static void main(String[] args) throws IOException {
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
X = Integer.parseInt(st.nextToken());
for (int i = 0; i <= N; i++) {
graph.add(new ArrayList<>());
}
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
int t = Integer.parseInt(st.nextToken());
graph.get(start).add(new Point(end, t));
}
// N -> X
int[] result = new int[N + 1];
for (int i = 1; i <= N; i++) {
int[] dist = dijkstra(i);
result[i] = dist[X];
}
// X -> N
int[] dist = dijkstra(X);
for (int i = 1; i <= N; i++) {
result[i] += dist[i];
}
int max = Arrays.stream(result).max().getAsInt();
bw.write(max + "\n");
bw.flush();
bw.close();
br.close();
}
static int[] dijkstra(int start) {
int[] dist = new int[N + 1];
boolean[] visited = new boolean[N + 1];
Arrays.fill(dist, INF);
PriorityQueue<Point> pq = new PriorityQueue<>((a, b) -> a.w - b.w);
pq.offer(new Point(start, 0));
dist[start] = 0;
while (!pq.isEmpty()) {
Point cur = pq.poll();
if (visited[cur.x]) {
continue;
}
visited[cur.x] = true;
for (Point next : graph.get(cur.x)) {
if (dist[next.x] > dist[cur.x] + next.w) {
dist[next.x] = dist[cur.x] + next.w;
pq.offer(new Point(next.x, dist[next.x]));
}
}
}
return dist;
}
static class Point {
int x;
int w;
Point(int x, int w) {
this.x = x;
this.w = w;
}
}
}
다른 사람 풀이 참고(효율적)
하지만, 다른 사람의 풀이를 보고 내가 작성한 알고리즘은 비효율적이라고 생각하게 되었다.
그래프를 정방향, 역방향 두개로 구성하여 해결할 수 있었다.
toX 는 원래 그래프고, fromX는 간선 방향을 뒤집은 그래프이다.
이렇게 그래프를 구성하면 다익스트라를 두 번만 수행하여 왕복거리를 구할 수 있다.
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
int t = Integer.parseInt(st.nextToken());
toX.get(start).add(new Point(end, t));
fromX.get(end).add(new Point(start, t));
}
int[] toXDist = dijkstra(toX); // N -> X
int[] fromXDist = dijkstra(fromX); // X -> N
실행 시간이 절반 이상 단축되었다.

전체 코드
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
static int N;
static int M;
static int X;
static int INF = 10000 * 100;
static List<List<Point>> toX = new ArrayList<>();
static List<List<Point>> fromX = new ArrayList<>();
public static void main(String[] args) throws IOException {
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
X = Integer.parseInt(st.nextToken());
for (int i = 0; i <= N; i++) {
toX.add(new ArrayList<>());
fromX.add(new ArrayList<>());
}
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
int t = Integer.parseInt(st.nextToken());
toX.get(start).add(new Point(end, t));
fromX.get(end).add(new Point(start, t));
}
int[] toXDist = dijkstra(toX); // N -> X
int[] fromXDist = dijkstra(fromX); // X -> N
int max = Integer.MIN_VALUE;
for (int i = 1; i <= N; i++) {
max = Math.max(max, toXDist[i] + fromXDist[i]);
}
bw.write(max + "\n");
bw.flush();
bw.close();
br.close();
}
static int[] dijkstra(List<List<Point>> graph) {
int[] dist = new int[N + 1];
boolean[] visited = new boolean[N + 1];
Arrays.fill(dist, INF);
PriorityQueue<Point> pq = new PriorityQueue<>((a, b) -> a.w - b.w);
pq.offer(new Point(X, 0));
dist[X] = 0;
while (!pq.isEmpty()) {
Point cur = pq.poll();
if (visited[cur.x]) {
continue;
}
visited[cur.x] = true;
for (Point next : graph.get(cur.x)) {
if (dist[next.x] > dist[cur.x] + next.w) {
dist[next.x] = dist[cur.x] + next.w;
pq.offer(new Point(next.x, dist[next.x]));
}
}
}
return dist;
}
static class Point {
int x;
int w;
Point(int x, int w) {
this.x = x;
this.w = w;
}
}
}
'Algorithm' 카테고리의 다른 글
| [백준] 1504. 특정한 최단 경로 (0) | 2025.09.25 |
|---|---|
| [백준] 1753. 최단경로 - JAVA (0) | 2025.09.23 |
| [백준] 13460. 구슬 탈출2 - JAVA (0) | 2025.09.18 |
| [백준] 14502. 연구소 - JAVA (0) | 2025.09.16 |
| [백준] 3190. 뱀 -JAVA (0) | 2025.09.14 |