[java]백준 11725- 트리의 부모 찾기, 트리 and DFS 깊이우선탐색

트리
노드와 에지로 연결된 그래프의 특수한 형태

 

트리의 특징
- 순환 구조(cycle)를 지니고 있지 않고, 1개의 루트 노드가 존재
- 루트 노드를 제외한 노드는 단 1개의 부모 노드를 가지고 있음
- 트리의 부분 트리(subtree) 역시 트리의 모든 특징을 따름

 

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

---

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

11725번: 트리의 부모 찾기

 

코드

 

package javaCodingTest;

import java.util.*;

public class j11725 {
	static ArrayList<Integer>[] nodes; // 연결된 노드 리스트
	static int[] parents_result; // 정답
	static boolean[] visited; // 방문 확인
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt(); // 노드 개
		visited= new boolean[N+1];  //방문 확인
		nodes = new ArrayList[N + 1]; //트리
		parents_result = new int[N + 1];  // 부모 노드 정답 
		for(int i=0;i<=N;i++) { // 초기화
			nodes[i]=new ArrayList<>();
		}
		for (int i = 1; i < N; i++) {// 연결된 노드 리스트에 저장
			int a = sc.nextInt();
			int b = sc.nextInt();
			nodes[a].add(b);
			nodes[b].add(a);
		}
		
		DFS(1);
		for(int i=2;i<=N;i++) {
			System.out.println(parents_result[i]);
		}
		
	}

	private static void DFS(int number) { // 부모노드 후 읽어서 부모노드 제외 자식노드!
		visited[number]=true;
		for(int i: nodes[number]) {
			if(!visited[i]) {
				parents_result[i]=number;
				DFS(i);
			}
		}
	}

}

 

풀이

DFS와 트리 사용

 

1이 루트 노드이므로 루트 노드부터 자식 노드를 읽어서 

루트 노드 외에는 자식 노드이므로 자식 노드의 자식 노드를 읽으며 부모 노드 입력