[BOJ][JAVA] 11725번: 트리의 부모찾기

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

11725번: 트리의 부모 찾기

import java.util.Arrays;
import java.util.Scanner;

class Main {
	static class Node {
		Integer data;
		Node l;
		Node r;
		Node p;
		public Node(int data) {
			this.data = data;
			this.l = null;
			this.r = null;
		}
		public Node(int data, Node p) {
			this.data = data;
			this.l = null;
			this.r = null;
			this.p = p;
		}
	}

	public static void main(String args[]) throws Exception {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		// 입력을 순서대로 받으면서, 먼저 입력된 노드가 존재하는 지 찾아야될 것 같음.
		Node[] tree = new Node[n+1];
		tree[1] = new Node(1); // 루트를 1이라고 가정했음.
		for (int i = 0; i < n; i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			if (tree[a] == null && tree[b] != null) {
				// 이러면 아직 노드에 들어오지않은것.
				tree[a] = new Node(a);
				tree[a].p = tree[b];
				if (a < b) { // 작으면 l, b가 부모
					tree[b].l = tree[a];
				} else {
					tree[b].r = tree[a];
				}
			} else if (tree[a] != null && tree[b] == null) {
				tree[b] = new Node(b);
				tree[b].p = tree[a];
				if (a > b) { // 작으면 l
					tree[a].l = tree[b];
				} else {
					tree[a].r = tree[b];
				}
			} else { // 둘다 null이면 그냥 하나 만들기
				if (a < b) {
					tree[a] = new Node(a);
					tree[b] = new Node(b);
					tree[b].p = tree[a];
					tree[a].r = tree[b];
				} else {
					tree[a] = new Node(a);
					tree[b] = new Node(b);
					tree[b].p = tree[a];
					tree[a].l = tree[b];
				}
			}
		}

		for (int i = 2; i <= n; i++) {
			System.out.println(tree[i].p.data);
		}
	}
}

 

 

---

오답노트(푸는 동안 사고과정 및 개선점)

부모 노드를 가리킬 p를 노드에 넣고 자식 노드를 만들 때 사용할 생성자를 추가로 넣어서 짜봤다. 아마 이미 자식이 있는데 또 덮어써서 npe가 나오는 것 같다...

그래서 노드 추가부분을 아래와 같이 바꿔봤는데도 오류가 나왔다.

tree[a] = new Node(a);
				tree[a].p = tree[b];
				if (a < b) { // 작으면 l, b가 부모 -> 자식이 이미 있다면? 그 자식과 값 비교하기
					if(tree[b].l != null) {
						tree[b].r = tree[a];
					}else {
						tree[b].l = tree[a];
					}
				} else {
					if(tree[b].r != null) {
						tree[b].l = tree[a];
					}else {
						tree[b].r = tree[a];
					}
				}

 

---

정답코드

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

class Main {
	static List<Integer>[] tree; 
	
	static int[] p;
	static boolean[] v;
	
	public static void main(String args[]) throws Exception {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		tree = new ArrayList[n+1];
		p = new int[n+1];
		v = new boolean[n+1];
		
		for(int i=0; i<n+1; i++) {
			tree[i] = new ArrayList<>();
		}
		for(int i=0; i<n-1; i++) {
			int node1 = sc.nextInt();
			int node2 = sc.nextInt();
			tree[node1].add(node2);
			tree[node2].add(node1);
		}
		find(1); // 1이 루트니까 
		for(int i=2; i<=n; i++) {
			System.out.println(p[i]);
		}
	}
	
	public static void find(int node) {
		v[node] = true;
		for(int i=0; i<tree[node].size(); i++) {
			int child = tree[node].get(i);
			if(!v[child]) {
				 p[child] = node;
				 find(child);
			}
		}
	}
}

ArrayList를 사용해서 Tree문제를 해결할 수도 있구나라는 걸 배운 문제다.

Node를 사용하지않으니까 재귀를 이용해서 값을 추가하고, 트리 구조 상 재귀로 탐색하는 게 수월하니까 재귀로 자식 노드를 얻고, 그 자식노드의 부모 노드값을 저장할 p 배열을 만들어서 현재 노드값을 p의 자식노드값 idx에 저장한다.

자고 일어나서 또 풀어볼 문제.

 

 

도움이 됐다면 댓글이나 공감 버튼 한 번씩 누르고 가주세요! 로그인 안해도 됩니다 ^_^