(백준/자바) 힌트문제2 05. 트리 - 백준 11725번 문제 : 트리의 부모 찾기

11725번: 트리의 부모 찾기 (acmicpc.net)

11725번: 트리의 부모 찾기

강의에서 막 트리를 배워서 응용을 해봤다.

 

- Node 클래스 : 각 노드의 data값과 부모노드 parent, 왼쪽 자식노드 left, 오른쪽 자식노드 right

class Node{
    int data;
    Node parent;
    Node left;
    Node right;

    public Node(int data, Node left, Node right, Node parent) {
        this.data = data;
        this.parent = parent;
        this.left = left;
        this.right = right;
    }
}

- BinaryTree클래스

 Constructor : 맨 처음 메인메소드에서 루트노드인 1과 총 노드의 갯수 size를 넣어주면 생성자로 루트노드 1을 생성하고 head가 가리키게함.

 searchNode 메소드 : data값이 들어오면 트리 안에서 일치하는 노드를 찾음.

 addNode 메소드 : data와 부모의 값을 받아서 부모노드의 left나 right에 새로운 노드를 생성해줌

 parentNode 메소드 : data가 들어오면 그 값의 부모노드를 찾아줌.

class BinaryTree{
    Node head;

    public BinaryTree(){}
    public BinaryTree(int data, int size) {
        Node[] nodes = new Node[size];
        nodes[0] = new Node(data, null, null, null);
        this.head = nodes[0];
    }

    public Node searchNode(int data) {
        Queue<Node> q = new LinkedList();
        q.add(this.head);

        while (!q.isEmpty()) {
            Node cur = q.poll();

            if (cur.data == data) {
                return cur;
            }
            if (cur.left != null) {
                q.offer(cur.left);
            }
            if (cur.right != null) {
                q.offer(cur.right);
            }
        }
        return null;
    }
    public void addNode(int data, int parent) {
       Node cur = this.searchNode(parent);

       if(cur.left == null){
           cur.left = new Node(data, null, null, cur);
       } else{
           cur.right = new Node(data, null, null, cur);
       }
    }

    public int parentNode(int data){
        Node cur = this.searchNode(data);
        return cur.parent.data;
    }
}

 

- 메인메소드가 있는 Tree_05 클래스

*노드의 수 N 값 입력받고

*정점의 수 N-1만큼 반복을 돌려서 두 값을 StringTokenizer로 찢어서 ArrayList peek에 저장 후 하나의 peek을 ArrayList list에 저장. (list가 ArrayList자료형을 가짐.)

*BinaryTree 객제 생성. 인자로 루트노드 1과 노드의 크기 N을 넣어줘서 초기화

*boolean 타입 visited 배열을 만들어서 이미 방문한 list의 요소는 또 방문하지 않게 함.

*q에 맨 처음 노드 추가후

  q가 비어있지 않으면 계속 반복.

 Node cur = q.poll(); 지정

list의 size만큼 for반복을 돌면서 한 리스트 안에 cur.data가 있는지 살펴봄.

있으면 정점 리스트에 요소값 2번만큼 반복을 도는데 현재 cur.data가 아닌 값이고 해당 리스트를 방문한 적이 없으면 리스트에서 cur.data가 아닌 값 ex) 맨처음cur.data가 1이고 리스트 안의 [1,6]리스트를 만났을 때 6을 addNode의 첫 번째 인자로 보내줌. 그러면 1의 자식노드로 6값을 가진 노드가 생성

 

q에 해당 노드를 찾아 넣어줌.

 

public class Tree_05 {
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        ArrayList <ArrayList> list = new ArrayList<>();

        StringTokenizer st;
        for(int i = 0; i < N - 1 ; i++) {
            st = new StringTokenizer(br.readLine());
            ArrayList <Integer> peek = new ArrayList<>();
            peek.add(Integer.parseInt(st.nextToken()));
            peek.add(Integer.parseInt(st.nextToken()));
            list.add(peek);
        }

        BinaryTree bt = new BinaryTree(1, N);
        Queue <Node> q = new LinkedList<>();
        boolean []visited = new boolean[N-1];
        q.add(bt.head);

        while(!q.isEmpty()){
            Node cur = q.poll();
            for (int j = 0; j < list.size(); j++) {
                if(list.get(j).contains(cur.data)){
                    for (int i = 0; i < 2; i++) {
                        if((int)list.get(j).get(i) != cur.data && !visited[j]){
                            bt.addNode((int)list.get(j).get(i),cur.data);
                            q.add(bt.searchNode((int)list.get(j).get(i)));
                        }
                    }
                    visited[j] = true;
                }
            }
        }
        for (int i = 2; i <= N ; i++) {
            System.out.println(bt.parentNode(i));
        }
    }
}

아무튼 근데 돌리자마자 런타임에러(NullPorinter) 발생

예제 결과 값은 잘 나왔다.

뭐가 문제일까 ..

 

---

8/8 다시시도

내가 한 방식대로 했어도 구할 수 있었을 것 같긴 한데 도무지 어떻게 손봐야할지 모르겠다.

이 문제에서는 bfs나 dfs로 푸는 문제라고 한다. 왜 그런가 생각해보면 트리가 이미 있고 , 각 트리의 정점 정보가 주어졌을 때 나는 그 트리를 순차적으로 따라 내려가면서 부모노드만 기록해주면 되기 때문이다. bfs로 구현해보았다.

 

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

class BinaryTree{
    static int N;
    static ArrayList <Integer>[] list;
    static int []parentsArr;
    public static void main(String args[]) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        parentsArr = new int[N + 1];

        list = new ArrayList[N + 1];
        for (int i = 1; i <= N ; i++) {
            list[i] = new ArrayList<>();
        }
        for (int i = 0; i < N - 1; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            list[x].add(y);
            list[y].add(x);
        }
        bfs(1);
        for (int i = 2; i <= N ; i++) {
            System.out.println(parentsArr[i]);
        }
    }
    public static void bfs(int n) {
        Queue <Integer> q = new LinkedList<>();
        boolean visited[] = new boolean[N + 1];
        visited[n] = true;
        q.offer(n);

        while (!q.isEmpty()) {
            int parent = q.poll();
            for (int i : list[parent]) {
                if (visited[i]) {
                    continue;
                }
                parentsArr[i] = parent;
                visited[i] = true;
                q.add(i);
            }
        }
    }
}

 - ArrayList [] : 인덱스는 노드 번호, 데이터는 자식노드 저장.

- bfs 메소드 Queue를 사용해서 루트노드 1부터 탐색해가며 부모노드를 찾고 parentsArr 배열에 저장해준다.

- parentsArr[] 은 각 인덱스가 노드로 부모노드의 값을 가지고 있음.