[알고리즘풀이]백준 15900: 나무 탈출 JAVA

목차

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

 

 

개요

이번에 알고리즘 스터디에서 JAVA를 이용해 백준 15900번 나무 탈출을 풀었습니다. 이를 정리해보고자 합니다.

15900번: 나무 탈출

 

본문

1) 문제

2) 과정

이번 문제는 3시간정도 걸려서 풀었습니다. 문제를 읽으면서 어려운건 아닌데..? 뭔가 찾으면 될 것 같은데...? 싶어서 찾다보니 꽤 시간이 걸렸네요. 처음에 풀어서 제출했는데 에러없이 돌아가서 안심했는데 제 순위가 100명중에 100등인걸보고 "아 이건 안된다. 어떻게 99등보다도 거의 2배 느리고 2배의 메모리를 쓰는거지?"란 생각이 들어 개선을 해나갔어요. 

 

그 결과 아래와 같은 변화로 실행 결과를 개선할 수 있었습니다.

// [1차] 메모리 437028 / 시간 1868
// - 속도 개선을 위해 split으로 쪼개지않고 StringTokenizer를 이용함.
// - 값 저장을 위해 HashSet을 배열에 넣는 대신 ArrayList로 변경함.
// [2차] 메모리 220616 / 시간 1016
// - 1차에 비해선 확실히 속도가 개선됨.
// - StringTokenizer의 힘에 깜짝 놀랐답니다...

 

제가 이번에 풀었던 방식은 leaf에서 root까지의 거리의 합을 bfs로 구하고, 이를 2로 나눴을 때 나머지가 1이면 Yes, 0이면 No를 출력하도록 만들었어요. 자세한 설명은 주석을 보면서 이해하시면 좋을 것 같습니다! 귀차니즘으로 DFS로 함수를 만드는대신 좀 더 길지만 BFS로 문제를 풀었더니 main함수 만으로 코드가 끝이납니다! 그래서 이번엔 평소와 달리 세부 설명을 드리는 대신 전체 코드만 보여드리고 끝마치려고 해요. 

 

3) 전체코드

그렇게 완성된 코드는 다음과 같습니다.

package sujeong.tree;

import java.util.*;
import java.io.*;

public class BOJ15900 {
    // Main
    public static void main(String[] args) throws IOException{
        // Input
        // get number of nodes
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        
        // initialize orgArr
        ArrayList<Integer>[] orgArr = new ArrayList[n + 1];
        for(int i=1;i<=n;i++) orgArr[i] = new ArrayList<>();
        
        // get info from the trunk line
        StringTokenizer st;
        for(int i=1;i<n;i++){
            st = new StringTokenizer(br.readLine());
            int one = Integer.parseInt(st.nextToken());
            int other = Integer.parseInt(st.nextToken());
            orgArr[one].add(other);
            orgArr[other].add(one);
        }

        // Initialize
        int sum = 0; // 각 leaf에서 root까지의 거리의 총합을 담을 변수

        Queue<int[]> q = new LinkedList<>(); // 노드번호와 건넌 다리수를 넘겨줄 큐
        q.add(new int[]{1,0}); // 노드번호, 건넌 다리수

        boolean[] visited = new boolean[n+1]; // 방문여부를 체크할 배열
        visited[1]=true; // 시작 루트인 1은 이미 방문했다고 셋팅


        // Logic
        // find the sum of distances(leaf -> root) using bfs
        while(!q.isEmpty()){
        	// get a nodeInfo
            int[] cur = q.poll();
            // check is leaf (leaf이라면 sum에 더해주고자 이를 체크할 boolean 변수를 만든것)
            boolean isLeaf = true;
            // chdeck has child and add child
            for(int child : orgArr[cur[0]]){
                // check visited
                if(visited[child]) continue;
                visited[child] = true;
                // it has child  = it isn't leaf
                isLeaf = false;
                // for next
                q.add(new int[]{child,cur[1]+1});
            }
            // if isLeaf is true -> add depth to sum
            if(isLeaf) sum+=cur[1];
        }


        // Output
        // 나머지가 1이면 먼저 시작한 성원이가 이길 수 있기 때문에 Yes
        // 나머지가 0이면 먼저 시작한 성원이가 이길 수 없기 떄문에 No
        System.out.println(sum%2==1?"Yes":"No");
    }
}

 

소요시간, 아이디어, 에러로그 등 더 자세히 이번 문제를 보고싶으시다면, 아래 깃헙 링크를 참고해주세요 :)

https://github.com/Park1122/Algorithm-Study/blob/master/sujeong/tree/BOJ15900.java

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