1248번 - 공통조상

문제의 저작권은 SW Expert Academy에 있습니다.

1. 문제
    1-1. 링크
    1-2. 문제 해석
2. 코드
3. 실행시간

 

 

 

---

 

 

1. 문제

1-1. 링크

SW Expert Academy

 

1-2. 문제 해석

공통조상과 서브 트리의 크기를 구하는 문제이다.

문제를 이해하는 건 크게 어렵지 않았고 서브 트리 크기 구할 때 자기 자신도 포함시키는 거? 외에 딱히 주의해야 할 점은 없었다.

 

• 공통 조상을 찾는 법

나는 주어진 두 정점을 번갈아 가며 부모 노드로 계속 쭉쭉 올라가도록 했다.

그러면서 지나온 부모노드를 ArrayList에 저장해두었다.

그러다가 둘 중 한 놈이 ArrayList에 저장된 부모 노드를 만나는 순간 공통 조상을 찾은 것으로 처리했다.

 

위 방법은 처음에 주어진 두 정점의 depth가 다를 때는 잘 되는데 같을 때는 무한루프에 빠진다.

그래서 루프를 돌 때마다 두 정점이 만나는지도 같이 검사해주었다.

 

• 서브 트리 크기 구하는 법

앞서 구한 공통 조상을 가지고 dfs를 하든 bfs를 하든 탐색하면서 카운트해주면 된다.

 

 

• 자료 저장

tree 배열

 

나는 3개의 행과 V+1개의 열로 이루어진 배열을 만들었다.

그리고 부모, 자식 관계를 이 배열에 저장했다.

물론 원하면 배열대신 LinkedList를 사용해도 된다.

 

2. 코드

public class Day11_1248_공통조상 {
	static ArrayList<Integer> parentList;
	static int[][] tree;
	static int ancestor;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int testCase = Integer.parseInt(br.readLine());
		StringTokenizer st;

		for (int tc = 1; tc <= testCase; tc++) {
			st = new StringTokenizer(br.readLine());
			int V = Integer.parseInt(st.nextToken());
			int E = Integer.parseInt(st.nextToken());
			int n1 = Integer.parseInt(st.nextToken());
			int n2 = Integer.parseInt(st.nextToken());
			
			tree = new int[V + 1][3];
			st = new StringTokenizer(br.readLine());
			while(st.hasMoreTokens()) {
				int parent = Integer.parseInt(st.nextToken());
				int child = Integer.parseInt(st.nextToken());
				
				// 부모에게 자식 할당(?)하기
				if(tree[parent][1] == 0)
					tree[parent][1] = child;
				else
					tree[parent][2] = child;
				
				// 자식에게 부모 할당하기
				tree[child][0] = parent;
			}
			
			parentList = new ArrayList<>();
			exploreAncestor(tree[n1][0], tree[n2][0]);
			System.out.println("#" + tc + " " + ancestor + " " + dfs(ancestor));
		}
	}

	// 공통 조상 찾기
	public static void exploreAncestor (int p1, int p2) {
		if(p1 != 0 && parentList.contains(p1)) {
			ancestor = p1;
			return;
		} else if( (p2 != 0 && parentList.contains(p2)) || p1 == p2) {
			ancestor = p2;
			return;
		}
		
		parentList.add(p1);
		parentList.add(p2);
		exploreAncestor(tree[p1][0], tree[p2][0]);
	}
	
	// 서브 트리 크기 알아내기
	public static int dfs(int cur) {
		int size = 0;
		
		if(tree[cur][1] != 0) 
			size += dfs(tree[cur][1]);
		
		if(tree[cur][2] != 0)
			size += dfs(tree[cur][2]);
		
		return size + 1;
	}
}

부모에게 자식할당하는 부분은 왼쪽 자식부터 채우고 오른쪽 자식 넣을 거라 if문이 있는 거고..

공통 조상 찾는 exploreAncestor에서는 재귀를 돌면서 부모 노드로 한 레벨씩 계속 올라간다.

찾는 로직은 [목차 1-2]에서 설명했고...

else if문에서 p1 == p2 부분이 없으면 depth가 같은 정점이 주어졌을 때 무한루프에 빠져버린다.

 

 

3. 실행시간

실행결과

 

 

 

 

 

 

---

💡 느낀 점

• 나는 언제쯤 1등을 할 수 있을까
• 이번 알고리즘 문제의 주제가 분할 정복과 백트래킹인데 이게 무슨 관련이 있는지 모르겠다. 조상을 찾으면 탐색을 멈췄으니 백트래킹? 모르겠다...

---