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

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

11725번: 트리의 부모 찾기

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

 

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

java

닫기 줄바꿈

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가 들어오면 그 값의 부모노드를 찾아줌.

java

닫기 줄바꿈

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에 해당 노드를 찾아 넣어줌.

 

java

닫기 줄바꿈

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로 구현해보았다.

 

java

닫기 줄바꿈

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[] 은 각 인덱스가 노드로 부모노드의 값을 가지고 있음.