[Baekjoon] 3584_가장 가까운 공통 조상

Gold IV

문제(출처: https://www.acmicpc.net/problem/3584)

---

< 가장 가까운 공통 조상 >

 

문제 풀이 & 생각

 

dfs를 활용하여 공통 조상을 찾는다.

 

 my solution (Java)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class _3584_ { // 가장 가까운 공통 조상
	static int root[], result;
	static boolean visited[];

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;

		int t = Integer.parseInt(bf.readLine());
		for (int i = 0; i < t; i++) {
			int n = Integer.parseInt(bf.readLine());

			root = new int[n + 1];
			visited = new boolean[n + 1];
			result = 0;

			for (int j = 0; j < n - 1; j++) {
				st = new StringTokenizer(bf.readLine());
				int a = Integer.parseInt(st.nextToken());
				int b = Integer.parseInt(st.nextToken());
				root[b] = a;
			}
			st = new StringTokenizer(bf.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());

			dfs(a);
			dfs(b);
			System.out.println(result);
		}
	}

	private static void dfs(int idx) {
		if (visited[idx]) {
			result = idx;
			return;
		}
		if (visited[root[idx]]) {
			result = root[idx];
			return;
		}
		visited[idx] = true;
		if (root[idx] != 0) {
			dfs(root[idx]);
		}
	}
}

 

Main

변수)
t : 테스트 케이스 개수
n : 트리를 구성하는 노드 수
root : 부모 노드 저장
visited : 방문 여부
result : 가장 가까운 공통 조상

 

- 테스트 케이스 개수(t) 입력

- 트리를 구성하는 노드 수(n) 입력

- 두 개의 숫자(a, b)를 입력받아 각 노드의 부모 노드 저장

- 가장 가까운 공통 조상을 구할 두 노드(a, b) 입력 후 각각 dfs 호출

- 가장 가까운 공통 조상(result) 출력

 

dfs

1) 현재 노드가 이미 방문한 곳이라면 가장 가까운 공통 조상 노드이므로 result 저장 후 종료

2) 자신의 부모 노드가 이미 방문한 곳이라면 가장 가까운 공통 조상 노드이므로 result 저장 후 종료

3) 방문 표시

4) 자신의 부모 노드가 0이 아니라면 부모가 존재하므로 dfs 호출

 

---

---