[백준/11725] 트리의 부모 찾기(DFS)

문제

---

루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

 

입력

---

첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.

 

출력

---

첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.

 

 

---

예제 입력 출력 예시

예제 입력 1 복사

7
1 6
6 3
3 5
4 1
2 4
4 7

 

예제 출력 1 복사

4
6
1
3
1
4

 

예제 입력 2 복사

12
1 2
1 3
2 4
3 5
3 6
4 7
4 8
5 9
5 10
6 11
6 12

 

예제 출력 2 복사

1
1
2
3
3
4
4
5
5
6
6

 

 

문제 풀이

문제 정리

문제를 쉽게 다시 정리하면 각 노드의 바로 위에 연결되어 있는 부모 노드를 찾는 문제였다.

1번 노드를 루트라고 가정하면, 1번 노드를 부모로 갖는 노드들은 바로 아래 연결되어 있는 구조이다.

DFS를 이용하여 1번 노드부터 모든 노드를 탐색하여 진행한다.

DFS에서 아래로 연결되어 있고 방문하지 않은 노드를 발견하면 자식노드로 처리하고 다음 자식노드에 대한 자식노드를 계속 찾아나가는 재귀함수로 DFS를 호출한다.

 

 

---

 

코드분석

static int n;
static int[] parent; // 각 노드의 대한 부보 노드 저장 배열
static ArrayList<Integer>[] list; // 각 노드별 연결되어 있는 노드들을 저장할 ArrayList배열,배열의 리스트가 들어감
static boolean[] visited; // 특정 노드르 방문처리할 배열

parent = new int[n + 1];
visited = new boolean[n + 1];
list = new ArrayList[n + 1];

• 노드 번호에 맞게 배열인덱스를 매칭하기 위해서 n+1 만큼에 크기로 배열을 생성한다.

 

for(int i=1; i<=n; i++) {
	list[i] = new ArrayList<>();
}
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());
		
	list[a].add(b); //ex 2 3
	list[b].add(a); //ex 3 2
}

• 각노드에 연결되어 있는 노드를 저장할 list를 만들기 위해 노드가 시작하는 인덱스 1번부터 리스트를 생성한다.
• 입력값이 주어지는 경우 입력받은 값을 배열, 리스트에 저장한다.
• 각각 바꿔서 2번 저장하는 이유는 기본 양방형으로 되어 있기 때문에 주석에 있는 예시와 같은 상황이기 때문에 뒤집은 경우를 해주는 것이다.

 

중요한 메인 DFS메소드

public static void dfs(int node) {
	visited[node] = true;
	for (int v : list[node]) {
		if (!visited[v]) {
			parent[v]=node;
			dfs(v);
		}
	}
}

• 그래프의 노드를 탐색하기 위해 사용되는 dfs 알고리즘 재귀함수이다!
• 매개값으로 들어온 node는 메서드가 호출될 때 방문했기 때문에 visited배열로 방문 여부를 나타낸다.
• 그래프의 인접 리스트를 표현하는 list에 대하여 반복문을 통해 node와 연결된 모든 노드의 목록을 나타낸다.
• 만약 아직 방문하지 않은 노드라면 현재 노드를 해당 노드의 부모로 설정하여 parent배열에 추가한다.
• 해당 노드로 이동해서 재귀함수를 통해 재귀적으로 탐색한다.

 

 

전체 코드

package practice;

import java.util.*;
import java.io.*;

public class Main {
	static int n;
	static int[] parent; // 각 노드의 대한 부보 노드 저장 배열
	static ArrayList<Integer>[] list; // 각 노드별 연결되어 있는 노드들을 저장할 ArrayList배열,재열의 리스트가 들어감
	static boolean[] visited; // 특정 노드르 방문처리할 배열

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		parent = new int[n + 1];
		visited = new boolean[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 a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());

			list[a].add(b); // ex 2 3
			list[b].add(a); // ex 3 2
		}
		dfs(1);

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

	public static void dfs(int node) {
		visited[node] = true;
		for (int v : list[node]) {
			if (!visited[v]) {
				parent[v] = node;
				dfs(v);
			}
		}
	}
}