[알고리즘풀이]백준 11265 : 끝나지 않는 파티 JAVA

목차

• 개요
•  본문
•  1) 문제
•  2) 과정
•  3) 코드 전체

 

 

개요

이번에 알고리즘 스터디에서 JAVA를 이용해 백준 11265번 끝나지 않는 파티를 풀었습니다. 이를 정리해보고자 합니다.

11265번: 끝나지 않는 파티

 

본문

1) 문제

2) 과정

shortest path니까 다익스트라 알고리즘을 사용하면 되겠지 싶었는데, 자꾸 시간초과가 발생하길래 다른 방법을 찾다 해당 문제를 플로이드 와샬 알고리즘으로 풀어야한단걸 알게되었습니다... 처음엔 오히려 다 구하면 오래 걸리지 않을까? 하며 반신반의했는데 오히려 더 빠르게 풀리는 걸 보고 제 자신의 무지함을 느꼈습니다.. 그렇게 4시간 정도 걸려서 문제를 해결했고 그 과정동안 받은 에러로그 및 개선과정을 깃헙에 적어뒀습니다 ! "내가 왜 틀렸지??" 싶은 분들은 한번쯤 방문하셔서 살펴보시면 도움이 될 것입니다!

 

해당 문제를 해결하면서 사용한 기본 아이디어는 "한 두개의 출발-목적지의 최단거리를 구하는게 아닌 다수의 경우의 최단거리를 구해야하기 때문에 플로이드 와샬로 최단거리를 dp에 모두 저장한다."였습니다.

 

그렇게 도출된 풀이 방식은 다음과 같습니다.
0) Input - 기본정보(n,m)를 입력받는다.
1) initialize dp array - dp에 입력받은 i->j까지의 시간을 담는다.
2) floyd warshall - 플로이드와샬 알고리즘으로 mid를 늘려가며 start에서 end까지의 dp(최단거리)값을 갱신해나간다.
3) output - 입력받은 출발지부터 도착지까지의 최단거리가 입력받은 최단거리보다 크다면 ans[0], 아니면 ans[1]을 출력한다.

 

상세 설명 구성은 Input, Logic, Output으로 구성했습니다. 주석으로도 충분히 많은 설명이 되어 있어 따로 내용을 적진않겠습니다!

 

2-1) Input

    // Constant
    static String[] ans = {"Stay here\n","Enjoy other party\n"};
    // Variable
    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;
    // Read Method 
    private static void readLine() throws IOException {st = new StringTokenizer(br.readLine()); }
    private static int nextInt() {return Integer.parseInt(st.nextToken());}
    // Main
    public static void main(String[] args) throws IOException {
        // Input
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        readLine();
        int n = nextInt(); // 파티장의 크기
        int m = nextInt(); // 서비스를 요청한 손님의 수
        // initialize dp array
        int[][] dp = new int[n][n]; // [i][j] 일때 i에서 j까지의 최단거리를 저장함.
        for(int i=0;i<n;i++){
            readLine();
            for(int j=0;j<n;j++) dp[i][j] = nextInt();
        }
    }

 

2-2) Logic 

	public static void main(String[] args) throws IOException {
    	// Logic
        for(int mid=0; mid<n;mid++){ // mid가 for문의 가장 바깥에 있어야하고, 작은수부터 늘려나가야 올바른 값이 나온다.
            for(int start=0;start<n;start++){
                for(int end=0;end<n;end++){
                    if(end==mid) continue; // end==mid일때의 값은 갱신할 필요가 없음.
                    dp[start][end] = Math.min(dp[start][end],dp[start][mid]+dp[mid][end]);
                }
            }
        }
    }

 

2-3) Output

        // Output
        for(int i=0;i<m;i++){
            readLine();
            bw.append(ans[dp[nextInt()-1][nextInt()]>nextInt() ? 0: 1]); 
        } bw.flush();

이번엔 BufferedWriter로 출력을해봤는데 sysout만 사용하는 것보다 속도가 많이 향상되어 맘에 들었습니다 ㅎㅎ!

 

3) 전체코드

그렇게 완성된 코드는 아래쪽에 링크된 깃헙 레포짓토리에 방문하여 확인해주세요!

소요시간, 아이디어, 에러로그 등 더 자세히 보실 수 있습니다.

https://github.com/Park1122/Algorithm-Study/blob/master/sujeong/shortest_path/BOJ11265.java

GitHub - Park1122/Algorithm-Study: 명지대학교 학생들이 모여서 만든 알고리즘 공부 및 코딩테스트 준비