트리

취업을 하고 자사의 솔루션을 학습한다는 핑계로 미뤄두었던 알고리즘 학습을 다시금 천천히 시작해보려 한다. 

오늘은 트리부터 시작해서 간단한 개념 정리와 문제풀이를 하려고 한다.

트리는 노드와 에지로 연결된 그래프의 특수한 형태로, 주요 특징은 아래와 같다. 

•  순환 구조를 가지고 있지 않고, 1개의 루트 노드가 존재한다. 
• 루트 노드를 제외한 나머지 노드는 반드시 단 하나의 부모노드를 가진다. 2개 이상의 부모 노드가 있다면 순환구조가 생길 수 밖에 없음
• 트리의 부분 트리 역시 트리의 모든 특징을 따른다. 

트리의 구성요소 

구성 요소	설명
노드	데이터의 index와 value를 표현하는 요소
에지	노드와 노드의 연결관계를 나타내는 선
루트 노드	트리에서 가장 상위에 존재하는 노드
부모 노드	두 노드 사이의 관계에서 상위 노드에 해당하는 노드
자식 노드	두 노드 사이의 관계에서 하위 노드에 해당하는 노드
리프 노드	트리에서 가장 하위에 존재하는 노드(자식 노드가 없음)
서브 트리	전체 트리에 속한 작은 트리

 

첫날이니 가볍게 쉬운 문제를 하나 풀어보자

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

11725번: 트리의 부모 찾기

 

트리를 구성하는 노드의 연결정보를 주고, 루트를 제외한 나머지 노드의 부모 노드를 구하는 문제이다. 
간단하게 생각해서 그래프의 구조를 먼저 생각해야 하는데, 인접리스트를 구성해서 트리의 구조를 그려보자.

출발지점은? 당연히 루트노드부터 시작하면 된다. 방문 배열과 정답배열을 만들어서 DFS탐색을 진행할 때, 시작 노드 바로 다음으로 탐색하는 노드가 자식 노드가 될 것이다. 즉, 시작노드가 다음 노드의 부모 노드가 되는 것이다.

package tree;

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

public class _11725_트리의부모찾기 {
	
	public static int n;
	public static boolean[] visited;
	public static int[] ans;
	public static ArrayList<ArrayList<Integer>> tree;
	
	public static void main(String args[]) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		n = Integer.parseInt(br.readLine());
		
		tree = new ArrayList<ArrayList<Integer>>(n+1);
		visited = new boolean[n+1];
		ans = new int[n+1];
		
		for(int i=0; i<=n; i++) {
			tree.add(new ArrayList<Integer>());
		}
		
		for(int i=0; i<n-1; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			
			//양방향 에지
			tree.get(a).add(b);
			tree.get(b).add(a);
		}
		
		//1번 노드에서 출발
		dfs(1);
		
		for(int i=2; i<=n; i++) {
			System.out.println(ans[i]);
		}
	}

	private static void dfs(int node) {
		visited[node] = true;
		
		for(int i : tree.get(node)) {
			if(visited[i]) continue;
			
			ans[i] = node;
			dfs(i);
		}
		
	}
}

배열의 크기를 n+1로 한 이유는 시작 노드번호가 제로베이스가 아닌 1번부터 시작하기 때문에 노드 번호를 맞춰주기 위해 반복문에서 +1하는 수고를 덜기 위함이다. 

인접리스트를 순회하면서 아직 방문하지 않은 노드가 인접 노드라면 현재 노드가 인접 노드의 부모 노드가 되는 것이다.