전에 푼 적 있었는데 긴가민가 하기도 했고,, 어느정도 정형화된 풀이가 있는 것 같아 정리하려고 오랜만에 포스트를 쓴다. 문제는 여기!
최소 공통 조상이 뭔지는 문제에 잘 나와 있어서 따로 설명을 더 하진 않겠다.
LCA
트리 만들기
좀 헷갈렸던게, 연결 관계가 주어지는 규칙이 따로 없이 그냥 부모-자식이든, 자식-부모든 지 맘대로 트리를 만들기 위한 입력값을 준다. 좀 고민을 해보다가 제한 시간을 보니까 아래와 같이 받아도 크게 문제 없을 것 같았다.
public class Main {
...
static class Edge {
int value1;
int value2;
Edge(int value1, int value2) {
this.value1 = value1;
this.value2 = value2;
}
}
public static void main(String[] args) throws Exception {
final int NUM_OF_NODES = Integer.parseInt(in.readLine());
// 트리 만들어주기 (루트는 항상 1)
Queue<Edge> edges = new LinkedList<>();
for(int cnt=0; cnt<NUM_OF_NODES-1; cnt++) {
st = new StringTokenizer(in.readLine());
int parent = Integer.parseInt(st.nextToken());
int child = Integer.parseInt(st.nextToken());
edges.add(new Edge(parent, child));
}
...
int[] parentOf = new int[NUM_OF_NODES+1];
parentOf[1] = 1; // 일관성을 위해 일단 루트의 부모도 루트로 처리
while (!edges.isEmpty()) {
Edge edge = edges.remove();
// 둘 다 트리에 포함되어 있지 않았다면
if (parentOf[edge.value1] == 0 && parentOf[edge.value2] == 0) {
// 다음에 다시 처리
edges.add(edge);
}
else if (parentOf[edge.value1] > 0) {
parentOf[edge.value2] = edge.value1;
}
else {
parentOf[edge.value1] = edge.value2;
}
}
// 1이 루트임을 표시
parentOf[1] = 0;
}
}요령은 별 거 없다. 그냥 지금까지 만들어 놓은 트리 정보에 엣지 양 끝 노드의 정보가 모두 없다면 아직 트리에 둘 다 나타난 적 없는 연결 정보이므로 나중에 처리해준다. 만약 있다면? 트리이기 때문에 무조건 둘 중 한 노드만 트리에 등장했을 것이므로 else if문과 else문을 사용했다.
또, 트리를 표현하는 방법이 여럿 있긴 하지만 공통 조상을 찾는 문제이므로 리프부터 루트까지 탐색하기 위해 특정 노드의 부모 노드를 기록했다.
최소 공통 조상 찾기
자 이제,, 주어지는 두 노드 쌍 여럿에 대해 최소 공통 조상(LCA, Lowest Common Ancestor)을 찾아주면 된다.
이것도 여러 방법이 있을 수 있겠지만 제일 직관적인건 부모 노드가 단 하나이므로, 두 노드가 공통의 부모를 만날 때까지 윗방향으로 계속 타고 올라가는 방법이다.
하지만 두 노드의 깊이(depth, level)가 다르다면 좀 골치가 아파진다. 두 노드가 루트까지 가는 경로는 각각 유일하므로 미리 구해놓고, 겹치는 부분 중 가장 먼저 겹치는 노드의 번호를 찾아야 하나 고민했었다. 휘유,,
그것보단 처음부터 두 노드가 같은 깊이에 있을 수 있도록 더 깊이 있는 노드를 위로 끌어 올려주고, 두 노드가 같은 부모 노드를 가리킬 때까지 동시에 한 층씩 위로 순회하는 방법이 더 쉬울 것이다.
아까는 부모-자식 간의 연결 관계만 초기화 해줬는데, 이젠 깊이까지 기록해보자.
public class Main {
...
static class Edge {
int value1;
int value2;
Edge(int value1, int value2) {
this.value1 = value1;
this.value2 = value2;
}
}
public static void main(String[] args) throws Exception {
final int NUM_OF_NODES = Integer.parseInt(in.readLine());
Queue<Edge> edges = new LinkedList<>();
...
int[] parentOf = new int[NUM_OF_NODES+1];
parentOf[1] = 1;
// 추가됨
int[] levelOf = new int[NUM_OF_NODES+1];
levelOf[1] = 1;
while (!edges.isEmpty()) {
Edge edge = edges.remove();
if (parentOf[edge.value1] == 0 && parentOf[edge.value2] == 0) {
edges.add(edge);
}
else if (parentOf[edge.value1] > 0) {
parentOf[edge.value2] = edge.value1;
// 추가됨
levelOf[edge.value2] = levelOf[edge.value1] + 1;
}
else {
parentOf[edge.value1] = edge.value2;
// 추가됨
levelOf[edge.value1] = levelOf[edge.value2] + 1;
}
}
// 1이 루트임을 표시
parentOf[1] = 0;
}
}알고리즘은 간단하다. 순회 도중에 트리에 없는 정보는 항상 지금 트리 상태를 기준으로 리프일 것이므로, 연결될 부모의 깊이에 1을 더해주면 그게 트리 안에서 해당 노드의 깊이가 된다.
다음으로는 두 노드의 깊이를 맞춰 최소 공통 조상 노드를 편하게 찾을 준비를 해보자.
public class Main {
public static void main(String[] args) throws Exception {
// 트리 만들기 + 깊이 기록하기
...
// 공통 조상을 출력할 횟수
final int NUM_OF_OPERATIONS = Integer.parseInt(in.readLine());
for(int op=0; op<NUM_OF_OPERATIONS; op++) {
st = new StringTokenizer(in.readLine());
// 공통 조상을 확인할 두 노드
int node1 = Integer.parseInt(st.nextToken());
int node2 = Integer.parseInt(st.nextToken());
// 두 노드의 깊이가 맞을 때까지 깊은 쪽을 끌어올려줌
while (levelOf[node1] != levelOf[node2]) {
if (levelOf[node1] > levelOf[node2]) {
node1 = parentOf[node1];
} else {
node2 = parentOf[node2];
}
}
}
...
}
}쉽다! 그냥 비교할 두 노드의 깊이가 같아질 때까지 한 쪽을 위로 끌어 올려주면 된다. 물론 코드를 간결하게 쓰려고 이렇게 쓴거지 줄어드는 쪽만 계속 줄어들고, 원래 더 얕았던 쪽은 그대로일 것이다.
이어서 높이가 같아진 두 노드의 조상을 비교하는데, 가장 먼저 만나는 조상이 최소 공통 조상일 것이다.
근데 여기서 하나를 놓쳐서 좀 헤맸다. 만약 노드 A와 노드 B에 대해 A가 B의 조상이면, A와 B의 최소 공통 조상은 A가 된다. 빠밤,,,
따라서 순회하기 전에, 같은 끌어올려진 B 노드가 A 노드와 같다면 A가 끌어올려졌든 B가 끌어올려졌든 지금 가리키고 있는 노드가 LCA가 된다. 이 조건을 고려해서 공통 조상이 나올 때까지 하나씩 위로 올라가며 서로의 부모를 비교해주면 문제 해결!
코드 전문은 아래와 같다.
import java.io.*;
import java.util.*;
public class Main {
static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
static StringBuilder out = new StringBuilder();
static StringTokenizer st;
static class Edge {
int value1;
int value2;
Edge(int value1, int value2) {
this.value1 = value1;
this.value2 = value2;
}
}
public static void main(String[] args) throws Exception {
final int NUM_OF_NODES = Integer.parseInt(in.readLine());
// 트리 만들어주기 (루트는 항상 1)
Queue<Edge> edges = new LinkedList<>();
for(int cnt=0; cnt<NUM_OF_NODES-1; cnt++) {
st = new StringTokenizer(in.readLine());
int parent = Integer.parseInt(st.nextToken());
int child = Integer.parseInt(st.nextToken());
edges.add(new Edge(parent, child));
}
int[] parentOf = new int[NUM_OF_NODES+1];
parentOf[1] = 1; // 일관성을 위해 일단 루트의 부모도 루트로 처리
int[] levelOf = new int[NUM_OF_NODES+1];
levelOf[1] = 1;
while (!edges.isEmpty()) {
Edge edge = edges.remove();
// 둘 다 트리에 포함되어 있지 않았다면
if (parentOf[edge.value1] == 0 && parentOf[edge.value2] == 0) {
// 다음에 다시 처리
edges.add(edge);
}
else if (parentOf[edge.value1] > 0) {
parentOf[edge.value2] = edge.value1;
levelOf[edge.value2] = levelOf[edge.value1] + 1;
}
else {
parentOf[edge.value1] = edge.value2;
levelOf[edge.value1] = levelOf[edge.value2] + 1;
}
}
// 1이 루트임을 표시
parentOf[1] = 0;
// 공통 조상을 출력할 횟수
final int NUM_OF_OPERATIONS = Integer.parseInt(in.readLine());
for(int op=0; op<NUM_OF_OPERATIONS; op++) {
st = new StringTokenizer(in.readLine());
// 공통 조상을 확인할 두 노드
int node1 = Integer.parseInt(st.nextToken());
int node2 = Integer.parseInt(st.nextToken());
// 두 노드의 깊이가 맞을 때까지 깊은 쪽을 끌어올려줌
while (levelOf[node1] != levelOf[node2]) {
if (levelOf[node1] > levelOf[node2]) {
node1 = parentOf[node1];
} else {
node2 = parentOf[node2];
}
}
// 끌어 올린 결과 같은 노드를 가리키고 있다면, 둘 중 한 노드가 다른 노드의 조상 노드
if (node1 == node2) {
out.append(node1).append('\n');
} else {
// 두 노드가 가리키는 부모가 같아질 떄까지 계속해서 함께 끌어올려줌
while (parentOf[node1] != parentOf[node2]) {
node1 = parentOf[node1];
node2 = parentOf[node2];
}
out.append(parentOf[node1]).append('\n');
}
}
System.out.println(out);
}
}응용 : 촌수계산
문제는 여기!
실은 이 문제를 먼저 풀다가 LCA 개념으로 깔끔하게 풀어보고 싶어서 먼저 풀고 왔다.
import java.io.*;
import java.util.*;
public class Main {
static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static final int INF = Integer.MAX_VALUE;
public static void main(String[] args) throws Exception {
final int NUM_OF_PEOPLE = Integer.parseInt(in.readLine());
// 촌수를 비교할 두 사람
st = new StringTokenizer(in.readLine());
int personA = Integer.parseInt(st.nextToken());
int personB = Integer.parseInt(st.nextToken());
// 부모-자식 관계의 수
final int NUM_OF_RELATIONSHIPS = Integer.parseInt(in.readLine());
int[] parentOf = new int[NUM_OF_PEOPLE+1];
for(int cnt=0; cnt<NUM_OF_RELATIONSHIPS; cnt++) {
st = new StringTokenizer(in.readLine());
int parent = Integer.parseInt(st.nextToken());
int child = Integer.parseInt(st.nextToken());
parentOf[child] = parent;
}
// 본인 위로 부모 정보가 없으면 level 1
int[] levelOf = new int[NUM_OF_PEOPLE+1];
// 두 사람이 친척 관계인지 확인
for (int person=1; person<=NUM_OF_PEOPLE; person++) {
int level = 0;
int current = person;
while (current != parentOf[current]) {
level++;
current = parentOf[current];
}
levelOf[person] = level;
}
// 촌수, 한 단계 끌어올려질 때마다 1촌씩 증가
int steps = 0;
// 두 노드의 깊이가 맞을 때까지 깊은 쪽을 끌어올려줌
while (levelOf[personA] != levelOf[personB]) {
steps++;
if (levelOf[personA] > levelOf[personB]) {
personA = parentOf[personA];
} else {
personB = parentOf[personB];
}
}
// 끌어 올린 결과 같은 노드를 가리키고 있다면, 촌수 계산 끝
if (personA == personB) {
System.out.println(steps);
} else {
// 두 노드가 가리키는 부모가 같아질 떄까지 계속해서 함께 끌어올려줌
while (parentOf[personA] != parentOf[personB]) {
personA = parentOf[personA];
personB = parentOf[personB];
// 둘 다 끌어올려졌으므로, 촌수는 2씩 증가
steps += 2;
}
// 이제 최소 형제 관계임은 확실하므로, 최소 공통 조상을 각각 경유하는 촌수 1씩 총 2를 우선 더해줌
steps += 2;
// 두 노드가 가리키는 노드가 0이면 공통 부모를 못 만났다는 의미이므로
// 두 사람이 속한 트리가 연결되어 있지 않음을 의미함
if (parentOf[personA] == 0) {
System.out.println(-1);
} else {
System.out.println(steps);
}
}
}
}
뭐 먹고 살지.