문제 설명
1238번: 파티
첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어
www.acmicpc.net
풀이 회고
문제에 따르면 각각의 1~N 마을에 사는 N명의 학생은 X(1 이상 ~ N 이하) 마을에 도착 후 본래 자기 마을로 돌아올 때 전체 걸리는 시간이 최단 시간으로 돌아오고자 합니다. 이때 문제에서 주어진 예시(테스트 케이스)에 대한 마을들 사이에 있는 M개의 단방향 도로들을 정리해보면 다음과 같습니다.
이때 각각의 학생들이 다시 자기 마을로 돌아오는데 걸리는 최소 시간을 정리해보면 다음과 같습니다.
- 마을 1에 사는 학생의 경우 마을 2를 경유해서 마을 1(자기가 사는 마을)로 돌아오는 최단 시간은 5(=1 + 4)입니다.
- (1 → 2), (2 → 1)
- 마을 2에 사는 학생의 경우 애초에 출발할 필요가 없으므로 최단 시간은 0입니다.
- 마을 3에 사는 학생의 경우 마을 2를 경유해서 마을 3으로 돌아오는 최단 시간은 9(=2+4+1+2)입니다.
- (3 → 1), (1 → 2), (2 → 1), (1 → 3)
- 마을 4에 사는 학생의 경우 마을 2를 경유해서 마을 4로 돌아오는 최단 시간은 10(=3+1+2+4)입니다.
- (4 → 2), (2 → 1), (1 → 3), (3 → 4)
이러한 조건들을 고려하면서 처음에 이 문제에 접근했을 때에는 DFS(깊이 우선 탐색)을 통해 접근했었습니다. M개 만큼 입력받은 모든 단방향의 도로들 즉, 주어진 모든 시작점과 끝점의 경로에서 탐색을 시작해 방문 처리하면서 X 마을을 경유하고 다시 방문 처리하면서 자기 마을로 돌아오도록 하여 각각의 학생별로 최단시간을 구하도록 했습니다. 하지만 결과는 메모리 초과였습니다. 이에 대한 풀이는 다음과 같았습니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
class Main {
static int n, m, t, home;
static int[] students;
static int[][] roads;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
t = Integer.parseInt(st.nextToken());
students = new int[n + 1];
for (int i = 1; i < n + 1; i++) {
if (i != t) {
students[i] = 100000000;
}
}
roads = new int[n + 1][n + 1];
boolean[][] visited;
while (br.ready()) {
st = new StringTokenizer(br.readLine());
roads[Integer.parseInt(st.nextToken())][Integer.parseInt(st.nextToken())] = Integer.parseInt(st.nextToken());
}
for (int i = 1; i < n + 1; i++) {
if (i == t) continue;
for (int j = 1; j < n + 1; j++) {
if (roads[i][j] != 0) {
home = i;
visited = new boolean[n + 1][n + 1];
go(i, j, roads[i][j], visited);
}
}
}
System.out.println(getMaxValue(students));
}
private static void go(int start, int target, int time, boolean[][] visited) {
if (visited[start][target]) {
return;
}
visited[start][target] = true;
visited[target][start] = true;
if (target == t) {
for (int i = 1; i < n + 1; i++) {
if (roads[target][i] != 0) {
boolean[][] newVisited = new boolean[n + 1][n + 1];
come(target, i,time + roads[target][i], newVisited);
}
}
return;
}
for (int i = 1; i < n + 1; i++) {
if (roads[target][i] != 0) {
go(target, i, time + roads[target][i], visited);
}
}
}
private static void come(int start, int target, int time, boolean[][] visited) {
if (visited[start][target]) {
return;
}
visited[start][target] = true;
visited[target][start] = true;
if (target == home) {
students[home] = Math.min(time, students[home]);
return;
}
for (int i = 1; i < n + 1; i++) {
if (roads[target][i] != 0) {
come(target, i, time + roads[target][i], visited);
}
}
}
private static int getMaxValue(int[] students) {
int result = 0;
for (int student : students) {
result = Math.max(student, result);
}
return result;
}
}
주어지는 학생의 수는 최대 1000명, 단방향 도로의 수는 최대 10000개인데, 각각의 모든 경로들을 재귀함수를 호출하면서 반복 탐색을 하다보니 콜 스택에 너무 많은 재귀함수가 쌓이지 않았을까(스택오버플로우) 하는 추정을 해보았습니다. 그리하여 나름대로 반복문으로 바꾸어 재시도해보았지만 결과는 시간 초과였습니다. 일단 해당 문제는 DFS로 푸는 것이 어렵다고 판단하여 방법을 바꾸고자 했습니다.
해당 문제에서 최종적으로 요구하는 것은 N명의 학생들 중 오고 가는데 가장 오래 걸리는 학생의 소요시간이지만 실상은 각각의 학생별로 오고 가는데 걸리는 최단 시간을 구해야 한다는 점이다. 그리하여 항상 공부 뒷전으로 미루고 있었던 최단경로 알고리즘이 번뜩 떠올랐습니다. 그리하여 알고리즘 관련 서적을 참고하여 최단경로 알고리즘을 살펴보았고 (나름대로) 친근했던 최단 경로 알고리즘이었던 '플로이드 워셜' 알고리즘을 적용하여 해결할 수 있었습니다. (근데 1초가 넘는데??!)
for (int i = 1; i < n + 1; i++) {
for (int j = 1; j < n + 1; j++) {
for (int k = 1; k < n + 1; k++) {
roads[j][k] = Math.min(roads[j][k], roads[j][i] + roads[i][k]);
}
}
}
위와 같이 플로이드 워셜 알고리즘을 통해 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구한 후 다음과 같이 각각의 학생별로 자기 자신의 마을에서 출발해 X 마을에 도착한 시간과 X 마을에서 출발해 다시 자기 자신의 마을에 도착한 시간을 구하여 이중에서 최댓값을 구하고자 했습니다.
for (int i = 1; i < n + 1; i++) {
students[i] = roads[i][t] + roads[t][i];
}
사실 이 문제의 경우 다익스트라 알고리즘을 이용해서도 풀 수 있을 것(더 효율적인 방법) 같은데, 아직까지 최단경로 파트에 대한 학습이 제대로 되어있지 않아 좀 더 학습을 진행한 이후에 도전해보고자 합니다. 💪 아울러 그동안 그래프하면 DFS 탐색과 BFS 탐색으로만 풀었었기에 최단경로 알고리즘으로 푼다는 생각을 못했었는데, 이번 기회에 최단 경로 파트 부분도 시간 내서 학습해보고자 합니다.
(2022. 7. 26. Update) 해당 문제는 다익스트라 알고리즘을 이용하여 다시 풀이하였습니다.(소스코드 하단 참고)
전체 소스 코드(플로이드 워셜)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
int t = Integer.parseInt(st.nextToken());
int[] students = new int[n + 1];
int[][] roads = new int[n + 1][n + 1];
for (int i = 1; i < n + 1; i++) {
for (int j = 1; j < n + 1; j++) {
if (i != j)
roads[i][j] = 1000001;
}
}
for (int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine());
roads[Integer.parseInt(st.nextToken())][Integer.parseInt(st.nextToken())] = Integer.parseInt(st.nextToken());
}
for (int i = 1; i < n + 1; i++) {
for (int j = 1; j < n + 1; j++) {
for (int k = 1; k < n + 1; k++) {
roads[j][k] = Math.min(roads[j][k], roads[j][i] + roads[i][k]);
}
}
}
for (int i = 1; i < n + 1; i++) {
students[i] = roads[i][t] + roads[t][i];
}
System.out.println(getMaxValue(students));
}
private static int getMaxValue(int[] students) {
int result = 0;
for (int student : students) {
result = Math.max(student, result);
}
return result;
}
}
전체 소스코드(다익스트라)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
class Main {
static int result = 0;
static final int INF = (int) 2e9;
static List<List<Node>> towns = new ArrayList<>();
static int[] times;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken()), m = Integer.parseInt(st.nextToken()), x = Integer.parseInt(st.nextToken());
times = new int[n + 1];
for (int i = 0; i <= n; i++) {
towns.add(new ArrayList<>());
}
int start, end, time;
for (int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine());
start = Integer.parseInt(st.nextToken());
end = Integer.parseInt(st.nextToken());
time = Integer.parseInt(st.nextToken());
towns.get(start).add(new Node(end, time));
}
int temp;
for (int i = 1; i <= n; i++) {
if (i == x) continue;
Arrays.fill(times, INF);
dijkstra(i);
temp = times[x];
Arrays.fill(times, INF);
dijkstra(x);
temp += times[i];
result = Math.max(result, temp);
}
System.out.println(result);
}
private static void dijkstra(int start) {
PriorityQueue<Node> pq = new PriorityQueue<>();
pq.add(new Node(start, 0));
times[start] = 0;
while(!pq.isEmpty()) {
Node node = pq.poll();
int time = node.getTime();
int now = node.getIndex();
if (times[now] < time) continue;
for (int i = 0; i < towns.get(now).size(); i++) {
int cost = times[now] + towns.get(now).get(i).getTime();
int index = towns.get(now).get(i).getIndex();
if (cost < times[index]) {
times[index] = cost;
pq.add(new Node(index, cost));
}
}
}
}
private static class Node implements Comparable<Node> {
private final int index;
private final int time;
public Node(int index, int time) {
this.index = index;
this.time = time;
}
public int getIndex() {
return this.index;
}
public int getTime() {
return this.time;
}
@Override
public int compareTo(Node other) {
return this.time - other.time;
}
}
}
참고자료
'Algorithm > BOJ' 카테고리의 다른 글
| [백준 - 2468] 안전 영역 - Java (0) | 2022.05.23 |
|---|---|
| [백준 - 1987] 알파벳 - Java (0) | 2022.05.19 |
| [백준 - 1018] 체스판 다시 칠하기 - Java (2) | 2022.05.12 |
| [백준 - 1931] 회의실 배정 - Java (0) | 2022.05.10 |
| [백준 - 7569] 토마토 - Java (0) | 2022.05.04 |