백준 1068 <트리>

 

일반적으로 제목이 트리다 형태가 트리가 라고 해서 접근하면 어려운 문제 중 하나이다.

 

일반적으로 노드의 구성은

이렇게 2진 트리로 구성이 되어 있는데 이문제는 2진 트리라고 주어 져있지 않기 때문에

이렇게 노드 ArrayList를 노드 안에 넣어주었다. 또한 안의 ArrayList를 <Node1>으로 해준 것은 이해를 돕기 위해서이니

ArrayList <Integer>로 인덱스 값만 넣어주면 되는 부분이다.

 

앞의 설명처럼 여러개의 노드를 자식으로 가질 수 있는 class를 만들어 주었다.

다음은 총 노드의 개수만큼 배열을 완성해주고  입력받은 값이 -1이 될 경우 시작점으로 선택을 하고 나머지는 입력값에 현재 위치를 추가해주었다.

 

※이 부분에서 중요한 점은 이문제는 하나의 트리이기때문에 -1 값이 두 개가 될 수 없다!

 

또한 이문제를 시작점을 기준으로 bfs를 했기 때문에

끝 위치가 시작점이면 count 값은 0 이기 때문에 같지 않을때 Queue에 넣어서 BFS를 시작하도록 했다.

 

중간에 예외처리를 한 부분은 마지막점이 다음에 오게 되면 그점을 Queue에 넣어 주지 않고

com은 자식이 몇명 있는지를 나타내는 것인데

이전에는 if절 위에 올라오게 해서 제거했음에도 불구하고 자식이 있다고 가정해 count를 더해 주지 않았었다.

 

일반적으로 트리를 구성하고 DFS 또는 BFS를 하는 방법에 대해 배울 수 있었던 문제이다.

 

트리의 구조형에 대해서 완벽하게 숙달을 할 수 있었고 트리로 DFS BFS를 하는 방법을 알 수 있는 문제였다.

 

전체 코드

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main{
	public static class Tr {
		int ni;
		ArrayList<Tr> a;

		public Tr(int ni) {
			this.ni = ni;
			a = new ArrayList<Tr>();
		}
	}

	static Tr t[];
	static int n, start, finish, count;
	static Queue<Tr> q = new LinkedList<Tr>();

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb = new Scanner(System.in);
		n = kb.nextInt();
		start = 0;
		finish = 0;
		t = new Tr[n];
		for (int i = 0; i < n; i++) {
			t[i] = new Tr(i);
		}
		for (int i = 0; i < n; i++) {
			int next = kb.nextInt();
			if (next == -1) {
				start = i;
			} else {
				t[next].a.add(t[i]);
			}
		}
		finish = kb.nextInt();
		if (finish != start) {
			q.add(t[start]);
		}
		bfs();
		System.out.println(count);

	}

	public static void bfs() {
		while (!q.isEmpty()) {
			Tr next = q.remove();
			int com=0;
			for (int i = 0; i < next.a.size(); i++) {
				Tr nextgo=next.a.get(i);
                com++;
				if(nextgo.ni==finish) {
					continue;
				}
				q.add(next.a.get(i));
			
			}
			if(com==0) {
				count++;
			}

		}
	}

}