백준 1068번 트리 JAVA 구현해보기

---

```

백준 1068번 트리 JAVA 구현해보기

```

이번 글을 통해 배워갈 내용

1.  백준 1068번 트리 풀이

---

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

1068번: 트리

 

 

백준 1068번 트리는 

난이도 골드 등급의 문제로서

 

트리가 주어질 때 노드를 하나 지우고 루트에서부터 연결된

잎사귀 노드(leaf node)를 구해주면 됩니다.

 

여기서 tree란 node들이 연결된 구조를 말합니다.

leaf node는 자식의 개수가 0개인 노드입니다.

 

---

30분 정도 위에 링크를 방문하셔서 풀어보시고

안 풀리시는 경우에만 아래 해답을 봐주시면 감사하겠습니다.

---

 

    private static class Node {
        private boolean isRoot = false;
        private List<Integer> childNode = new ArrayList<>();
    }

private static final List<Node> nodes = new ArrayList<>();
private static boolean hasMoreNodes = true;

private static void createNodes(int treeElemSize) {
    for (int i = 0; i < treeElemSize; i++) {
        nodes.add(new Node());
    }
}

private static int initChildNodes(StringTokenizer st) {
    int idx = 0;
    int rootIdx = 0;

    while (st.hasMoreTokens()) {
        final int curParentNum = Integer.parseInt(st.nextToken());

        // 루트 노드라면
        if (curParentNum == -1) {
            nodes.get(idx).isRoot = true;
            rootIdx = idx;
        }
        // 루트 노드가 아니라면
        else {
            nodes.get(curParentNum).childNode.add(idx);
        }
        idx++;
    }
    return rootIdx;
}

 

노드들을 생성하고

노드리스트를 만들어서 노드를 넣어줍니다.

해당 노드리스트의 index가 노드의 번호입니다.

자식 노드들을 부모 기준으로 list 형식으로 입력받습니다.

노드가 루트노드인지 아닌지는 노트 내부에 boolean을 두어서 판별하였습니다.

 

private static void deleteOneNode(int idxToDelete) {
    // 루트 노드라면
    if (nodes.get(idxToDelete).isRoot) {
        nodes.get(idxToDelete).childNode = new ArrayList<>();
        hasMoreNodes = false;
        // 루트 노드가 아니라면
        // 현위치의 부모를 찾아서 자식 제거
    } else {
        nodes.stream()
                .filter(node -> node.childNode.contains(idxToDelete))
                .findAny().ifPresent(nodeToProcess -> nodeToProcess.childNode.removeIf(curNum -> curNum == idxToDelete));
    }
}

입력받은 노드를 지워줍니다.

 

private static int findLeafNumber(int rootIdx) {

    // 잎 갯수
    int leafCount = 0;

    // 방문할 리스트
    List<Integer> visitLists = new ArrayList<>();
    visitLists.add(rootIdx);

    while (hasMoreNodes) {

        int lastIdx = visitLists.size() - 1;
        int curNodeIdx = visitLists.remove(lastIdx);

        // 잎노드면 카운트를 추가한다.
        if (nodes.get(curNodeIdx).childNode.isEmpty()) {
            leafCount++;
        }

        // 자식 노드를 더한다.
        visitLists.addAll(nodes.get(curNodeIdx).childNode);


        if (visitLists.isEmpty()) {
            hasMoreNodes = false;
        }
    }
    return leafCount;
}

리프 노드의 갯수를 찾아줍니다.

 

 

전체 코드는 아래와 같습니다.

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

public class Main {

    private static class Node {
        private boolean isRoot = false;
        private List<Integer> childNode = new ArrayList<>();
    }

    private static void createNodes(int treeElemSize) {
        for (int i = 0; i < treeElemSize; i++) {
            nodes.add(new Node());
        }
    }

    private static int initChildNodes(StringTokenizer st) {
        int idx = 0;
        int rootIdx = 0;

        while (st.hasMoreTokens()) {
            final int curParentNum = Integer.parseInt(st.nextToken());

            // 루트 노드라면
            if (curParentNum == -1) {
                nodes.get(idx).isRoot = true;
                rootIdx = idx;
            }
            // 루트 노드가 아니라면
            else {
                nodes.get(curParentNum).childNode.add(idx);
            }
            idx++;
        }
        return rootIdx;
    }

    private static void deleteOneNode(int idxToDelete) {
        // 루트 노드라면
        if (nodes.get(idxToDelete).isRoot) {
            nodes.get(idxToDelete).childNode = new ArrayList<>();
            hasMoreNodes = false;
            // 루트 노드가 아니라면
            // 현위치의 부모를 찾아서 자식 제거
        } else {
            nodes.stream()
                    .filter(node -> node.childNode.contains(idxToDelete))
                    .findAny().ifPresent(nodeToProcess -> nodeToProcess.childNode.removeIf(curNum -> curNum == idxToDelete));
        }
    }

    private static int findLeafNumber(int rootIdx) {

        // 잎 갯수
        int leafCount = 0;

        // 방문할 리스트
        List<Integer> visitLists = new ArrayList<>();
        visitLists.add(rootIdx);

        while (hasMoreNodes) {

            int lastIdx = visitLists.size() - 1;
            int curNodeIdx = visitLists.remove(lastIdx);

            // 잎노드면 카운트를 추가한다.
            if (nodes.get(curNodeIdx).childNode.isEmpty()) {
                leafCount++;
            }

            // 자식 노드를 더한다.
            visitLists.addAll(nodes.get(curNodeIdx).childNode);


            if (visitLists.isEmpty()) {
                hasMoreNodes = false;
            }
        }
        return leafCount;
    }

    private static final List<Node> nodes = new ArrayList<>();
    private static boolean hasMoreNodes = true;


    public static void main(String[] args) throws IOException {
        final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        final int treeElemSize = Integer.parseInt(br.readLine());
        final StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        // 노드 생성
        createNodes(treeElemSize);

        // 자식 노드 초기화
        int rootIdx = initChildNodes(st);

        final int idxToDelete = Integer.parseInt(br.readLine());

        // 노드 하나 제거
        deleteOneNode(idxToDelete);

        // 노드 잎 갯수
        System.out.println(findLeafNumber(rootIdx));
    }
}

 

 

읽어주셔서 감사합니다

 

무엇인가 얻어가셨기를 바라며

 

오늘도 즐거운 코딩 하시길 바랍니다 ~ :)

 

---