[알고리즘풀이]백준 1068 : 트리 JAVA

목차

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

 

 

개요

이번에 알고리즘 스터디에서 JAVA를 이용해 백준 1068번 트리를 풀었습니다. 이를 정리해보고자 합니다.

1068번: 트리

 

본문

1) 문제

2) 과정

이번주에 풀었던 과제들은 대부분 쉬웠어요. 

[알고리즘풀이]백준 1240 : 노드 사이의 거리 JAVA

 

[알고리즘풀이]백준 3584: 가장 가까운 공통 조상 JAVA

 

9489만 빼고... 그건 진짜 힘들고,,, 머리에 쥐나는 기분이었어요......

[알고리즘풀이]백준 9489 : 사촌 JAVA

 

 

이번 문제도 푸는데 40분 정도 걸렸습니다. 조금 어려웠던 건 일직선 상으로 트리가 위치했을 때 값이 제대로 출력안되어서 틀렸습니다를 받았는데요. 이 질문함 덕분에 해결했습니다(https://www.acmicpc.net/board/view/67627)

 

제가 문제를 풀며 사용했던 아이디어는 다음과 같습니다.

 1. 입력으로 트리를 만들때 orgArr[부모]에 arrayList를 이용해 자식들을 담도록 한다.
 2. BFS로 root부터 탐색을 진행하며 rmNum(지워질 노드의 숫자)가 나타나면 넘어가고 leafNode를 찾으면 leafNum을 추가한다.
 3. rmNum 노드도 leaf 노드도 아니라면 탐색을 위해 큐에 추가해준다.
 4. 탐색을 마친 뒤 leafNum을 출력하며 끝낸다.

 

Input,Logic,Output으로 문제 풀이를 나눠볼게요 :) 주석으로 충분히 설명한 것 같아서 따로 설명은 달지 않겠습니다.

 

2-1) Input

        // Input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine()); // n(노드의 수)
        int root = 0; // root값을 담을 변수

        ArrayList<Integer>[] orgArr = new ArrayList[n]; // orgArr[부모번호](자식들...)로 담기위한 구조
        StringTokenizer st = new StringTokenizer(br.readLine());        
        for(int i=0;i<n;i++){
            // input value
            int input = Integer.parseInt(st.nextToken());
            // if parent node -> set root i
            if(input==-1) root = i;
            else{ 
                // if orgArr[input]==null 아직 아무런 자식도 추가되지 않아 new가 안되어있다면 new를 해줌.
                if(orgArr[input]==null) orgArr[input]=new ArrayList();
                // orgArr[부모]에 i(자식)들 더해준다.
                orgArr[input].add(i);
            }
        }
        int rmNum = Integer.parseInt(br.readLine());

 

2-2) Logic & Output

        // Logic
        int leafCnt = 0; // leaf의 수를 담을 변수이자 정답
        Queue<Integer> q = new ArrayDeque<>(); // bfs로 자식을 탐색하기 위한 큐
        q.add(root); // root부터 시작이니 root를 담아준다.
        // do bfs
        while(!q.isEmpty()){
            // get a number
            int cur = q.poll();
            // check Condition
            // 현재 숫자가 지워질 노드의 번호라면 더이상 leaf나 q에 추가할 필요없으니 넘어감.
            if(cur == rmNum) continue; 
            // 현재 숫자가 자식이 없거나, 현재 숫자의 자식이 하나인데 그 자식이 지워질 번호라면 leaf수를 늘리고 넘어감.
            if(orgArr[cur]==null || (orgArr[cur].size()==1 && orgArr[cur].get(0)==rmNum)){
                leafCnt++;
                continue;
            }
            // add child into q for next loop
            for(int c : orgArr[cur]) q.add(c);
        }

        // Output
        System.out.println(leafCnt);

 

 

3) 전체코드

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

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

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

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