모각코 4회차(240123)

[백준/BOJ] 1238번 파티 (자바/Java)

 

https://www.acmicpc.net/problem/1238

1238번: 파티

---

1. 문제

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 

4 8 2
1 2 4
1 3 2
1 4 7
2 1 1
2 3 5
3 1 2
3 4 4
4 2 3

예제 출력 1 

10

 

 

2. 풀이

최단 경로 알고리즘 중에서 다익스트라가 기억나지 않아, 벨만 포드와 플로이드 와샬 중에서 안전하게 플로이드 와샬을 구현해보았다.

 

입력 범위와 시간복잡도를 고려하였을 때, 1초 내에 연산이 가능할 것이라고 판단하여서 선택하였다. 플로이드 와샬은 다익스트라와 벨만 포드의 단점을 보완하지만 시간복잡도가 높다는 단점이 있지만 구현이 간편하여 이 문제에서는 시간복잡도에 구애받지 않을 것 같아 선택했다.

 

플로이드 와샬의 코드가 기억나지 않았지만 알고리즘의 아이디어부터 생각해보면서 구현을 해나갔다. 다행이 문제를 해결할 수 있었다.

2023.10.16 - [CS/Algorithm] - [알고리즘] Floyd-Warshall 알고리즘이란?

[알고리즘] Floyd-Warshall 알고리즘이란?

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int N;
    static int M;
    static int X;
    static int[][] map;
    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());
        X = Integer.parseInt(st.nextToken())-1;

        map = new int[N][N];
        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                map[i][j] = Integer.MAX_VALUE;
            }
            map[i][i] = 0;
        }

        int start, end, time;
        for(int i=0; i<M; i++){
            st=  new StringTokenizer(br.readLine());
            start = Integer.parseInt(st.nextToken())-1;
            end = Integer.parseInt(st.nextToken())-1;
            time = Integer.parseInt(st.nextToken());

            map[start][end] = time;
        }

        for(int k=0; k<N; k++){
            // i를 거쳐서 갈 수 있는 경로들이 최소가 되도록 update
            for(int i=0; i<N; i++){
                if(i==k) continue; // 자기 자신은 자기 자신을 거쳐갈 수 없음.

                for(int j=0; j<N; j++){
                    if(i==j || j==k) continue; // 자기 자신을 가는 경로는 0임.
                    if(map[i][k] == Integer.MAX_VALUE || map[k][j] == Integer.MAX_VALUE) continue; // overFlow 방지

                    if(map[i][j] > map[i][k] + map[k][j]){
                        map[i][j] = map[i][k] + map[k][j];
                    }
                }
            }
        }

        int maxTime = -1;
        int usedTime = 0;
        for(int i=0; i<N; i++){
            if(i == X) continue; // 자기 자신은 이동하지 않으므로 시간을 소요하지 않음.

            usedTime = map[i][X] + map[X][i];
            maxTime = Math.max(maxTime, usedTime);
        }

        System.out.println(maxTime);
    }
}

 

3. 결과

 

4. 총평

 - 학부시간에 배웠던 알고리즘을 간과하지 말고 아이디어라도 잘 기억해서 나중에 코테에서 나온다면 직접 구현해서 풀 수라도 있어야겠다