최소 공통 조상(LCA) Lowest Common Ancestor

[WonYong-Jang]

Lowest Common Ancestor

가장 가까운 위치의 공통 조상을 찾는데 쓰이거나 두 노드의 가장 가까운 거리를 찾는데 사용

LCA

• 단순하게 loop 를 이용 / 시간초과 날 가능성 / O(N)
• parent : 노드의 부모노드를 저장
• depth : 트리의 깊이를 저장

시나리오

1. 두 노드가 주어지게 되면 두 노드의 깊이를 구함 ( depth 배열 이용 )
2. 두 노드들 중 더 깊은 곳에 있는 노드를 더 얖은 곳에 있는 노드 위치까지 끌어 올려줌
   2-1) 부모노드로 계속 한칸씩 끌어올리면서 깊이를 확인 / 두 노드가 같은 깊이 상태까지
3. 두 노드 깊이가 같으나 두 노드의 값이 같지 않다면 두 노드 모두 부모노드로 끌어올리면서 같은지 확인
   3-1) 두 노드가 같아질때가 최소 공통 조상

public class baek11437 {

	static int N, M;
	static ArrayList<ArrayList<Integer>> adj = new ArrayList<ArrayList<Integer>>();
	static int[] parent = new int[50005];
	static int[] depth = new int[50005];
	public static void main(String[] args) throws IOException {

		int dx=0, dy=0;
		for(int i=1; i<= N-1; i++)
		{
			st = new StringTokenizer(br.readLine());
			dx = Integer.parseInt(st.nextToken());
			dy = Integer.parseInt(st.nextToken());
			adj.get(dx).add(dy);
			adj.get(dy).add(dx);
		}
		
		dfs(1,1,0); // parent, depth 배열 완성하기 
		
		st = new StringTokenizer(br.readLine());
		M = Integer.parseInt(st.nextToken());
		for(int i=1; i<= M; i++)
		{
			st = new StringTokenizer(br.readLine());
			dx = Integer.parseInt(st.nextToken());
			dy = Integer.parseInt(st.nextToken());
			
			int xDepth = depth[dx];
			int yDepth = depth[dy]; // 각각의 depth 가져와서 확인!
			
			while(xDepth > yDepth) // x 가 클 경우 낮춰주면서 부모노드로 이동 
			{
				dx = parent[dx];
				xDepth--;
			}
			
			while(xDepth < yDepth)
			{
				dy = parent[dy];
				yDepth--;
			}
			
			while( dx != dy ) // 같은 depth 일때 둘다 부모노드로 올라가면서 찾기 
			{
				dx = parent[dx];
				dy = parent[dy];
			}
			
			System.out.println(dx);
		}
	}
	public static void dfs(int cur, int d, int p) // 현재 노드, 깊이, 부모 노드 
	{
		depth[cur] = d;
		parent[cur] = p;
		for(int next : adj.get(cur))
		{
			if(next != p) // 해당 노드에서 depth 가 더 깊은 곳으로만 이동 / 부모노드로 이동하지 않는다
			{
				dfs(next, d+1, cur); // 다음 depth 로 이동 / 현재 노드가 부모 노드가 됨 
			}
		}
	}
}

LCA2

DP를 이용하여 해결

• 시간 복잡도 O(logN) / 쿼리가 함께 존재할 경우 O(MlogN)

시나리오

1. 깊이가 더 깊은 노드를 깊이가 더 낮은 노드까지 노드를 올려준다

• 이때 노드의 조상들을 이용 / 2^k 번째 조상 중 가장 큰 조상부터 조사함

public class baek11438 {

	static int N, M, max_level;
	static final int MAX_NODE = 100005;
	static int[] depth = new int[MAX_NODE]; // 노드의 깊이(레벨) 
	static int[][] parent = new int[MAX_NODE][20]; // parent[x][y] :: x 의 2^y번째 조상을 의미  
	static ArrayList<ArrayList<Integer>> adj = new ArrayList<ArrayList<Integer>>(); 
	public static void main(String[] args) throws IOException {

		max_level = 0;
		int result =1;
		while(result < N) // max_level 구하기 
		{
			result *= 2;
			max_level++;
		}
		
		int dx =0, dy=0;
		
		depth[0] = -1; // 루트 노드 깊이를 0으로 만들어 주기 위해 ! 
		makeTree(1,0); // 트리 만들기 !! 
		
		st = new StringTokenizer(br.readLine());
		M = Integer.parseInt(st.nextToken());
		for(int i=1; i<= M; i++)
		{
			st = new StringTokenizer(br.readLine());
			dx = Integer.parseInt(st.nextToken());
			dy = Integer.parseInt(st.nextToken());
			
			if(depth[dx] != depth[dy]) // 두 노드의 깊이가 다를 경우 같게 맞춰 줘야함 
			{
				if(depth[dx] > depth[dy]) // dy 의 깊이가 더 크다라고 가정하고 끌어올린후 깊이를 같게 만든다 
				{ 
					int tmp = dx;
					dx = dy;
					dy = tmp;
				}
				
				for(int k = max_level; k >= 0; k--)
				{
					if(depth[dx] <= depth[parent[dy][k]])
						dy = parent[dy][k];
				}
			}
			
			int lca = dx;
			
			if(dx != dy)
			{
				for(int k = max_level; k >= 0; k--)
				{
					if(parent[dx][k] != parent[dy][k])
					{
						dx = parent[dx][k];
						dy = parent[dy][k];
					}
					lca = parent[dx][k];
				}
			}
			bw.write(lca+"\n");
		}
		bw.flush();
	}
	public static void makeTree(int cur, int p)
	{
		depth[cur] = depth[p] + 1; // 부모 노드의 깊이에서 +1 ==> 현재 노드 깊이 
		parent[cur][0] = p; // 바로 위 부모 노드 
		
		/*
		  	Node 의 2^i 번째 조상은 tmp 의 2^(i-1) 번째 조상의 2^(i-1)번째 조상과 
		  	같다는 의미
		  	예 ) i =3 일때
		  	Node의 8번째 조상은 tmp(Node의 4번째 조상)의 4번째 조상과 같다.
		  	i=4 일때는 Node 16번째 조상은 Node 의 8번째 조상(tmp)의 8번째와 같다.
		 */
		for(int i=1; i<= max_level; i++)
		{
			int tmp = parent[cur][i-1];
			parent[cur][i] = parent[tmp][i-1];
		}
		
		for(int next : adj.get(cur)) // 자식 노드 내려가면서 확인 
		{
			if(next != p) // 사이클 방지 아래로만 내려가기 
			{
				makeTree(next, cur);
			}
		}
	}
	
}

LCA2 를 이용한 정점들간의 거리

• dist[parent] 배열의 의미는 1(root)에서 부모까지 내려온 거리이고 cost 값은 부모와 자식 노드의 거리 둘을 더하게 되면 1에서 자식까지의 거리를 생성 가능
  ==> dist[cur] = dist[parent] + cost

public class Main {

	static int N, M, max_level;
	static int max_node = 40005;
	static int[][] par = new int[max_node][20];
	static int[] depth = new int[max_node];
	static int[] cost = new int[max_node];
	static ArrayList<ArrayList<Node>> adj = new ArrayList<ArrayList<Node>>();
	public static void main(String[] args) throws IOException {

		max_level = 0;
		int mul = 1;
		while(N > mul) { // 확인 
			mul *= 2;
			max_level++;
		}
		
		int dx = 0, dy = 0, c = 0;
		for(int i=1; i<= N-1; i++)
		{
			st = new StringTokenizer(br.readLine());
			dx = Integer.parseInt(st.nextToken());
			dy = Integer.parseInt(st.nextToken());
			c = Integer.parseInt(st.nextToken());
			adj.get(dx).add(new Node(dy, c));
			adj.get(dy).add(new Node(dx, c));
		}
		depth[0] = -1;
		dfs(1, 0, 0);
		
		st = new StringTokenizer(br.readLine());
		M = Integer.parseInt(st.nextToken());
		for(int i=1; i<= M; i++)
		{
			st = new StringTokenizer(br.readLine());
			dx = Integer.parseInt(st.nextToken());
			dy = Integer.parseInt(st.nextToken());
			
			int result = 0;
			int rdx = dx, rdy = dy;
			if(depth[dx] != depth[dy])
			{
				if(depth[dx] > depth[dy])
				{
					int tmp = dx;
					dx = dy;
					dy = tmp;
				}
				
				for(int k = max_level; k >= 0; k--)
				{
					if(depth[dx] <= depth[par[dy][k]]) {
						dy = par[dy][k];
					}
				}
			}
			
			int lca = dx;
			
			if(dx != dy)
			{
				for(int k = max_level; k >= 0; k--)
				{
					if(par[dx][k] != par[dy][k])
					{
						dx = par[dx][k];
						dy = par[dy][k];
					}
					lca = par[dx][k];
				}
			}
			
			result = ( cost[rdx] + cost[rdy] ) - ( 2 * cost[lca] );
			bw.write(result+"\n");
		}
		bw.flush();
	}
	public static void dfs(int cur, int p, int c)
	{
		depth[cur] = depth[p] + 1;
		cost[cur] = c;
		par[cur][0] = p;
		
		int tmp = 0;
		for(int i=1; i<= max_level; i++)
		{
			tmp = par[cur][i-1];
			par[cur][i] = par[tmp][i-1];
		}
		
		for(Node next : adj.get(cur))
		{
			if(next.dx != p)
			{
				dfs(next.dx, cur, next.cost + c);
			}
		}
	}
}

출처 링크 : https://www.crocus.co.kr/660

[WonYong-Jang]

추천 문제

11438번: LCA 2

1761번: 정점들의 거리

8012번: Byteasar the Travelling Salesman

15480번: LCA와 쿼리 (★)

1396번: 크루스칼의 공 (★)

[WonYong-Jang]

3176번 도로 네트워크

public class Main {

	static int N, K, max_level;
	static final int max_node = 100005;
	static int[][] maxDp = new int[max_node][20];
	static int[][] minDp = new int[max_node][20];
	static int[][] parent = new int[max_node][20];
	static int[] depth = new int[max_node];
	static ArrayList<ArrayList<Node>> adj = new ArrayList<ArrayList<Node>>(); 
	public static void main(String[] args) throws IOException {
		
		depth[0] = -1;
		dfs(1,0,0);
		
		make_dp();
		
		st = new StringTokenizer(br.readLine());
		K = Integer.parseInt(st.nextToken());
		for(int i=1; i<= K; i++)
		{
			st = new StringTokenizer(br.readLine());
			dx = Integer.parseInt(st.nextToken());
			dy = Integer.parseInt(st.nextToken());
			
			int tx = dx, ty = dy;
			int ansMax = -1, ansMin = Integer.MAX_VALUE;
			if(depth[dx] != depth[dy] )
			{
				if(depth[dx] > depth[dy]) {
					int tmp = dx;
					dx = dy;
					dy = tmp;
				}
				
				for(int k = max_level; k >= 0; k--)
				{
					if(depth[dx] <= depth[parent[dy][k]]) 
					{
          // 주의 dy 갱신하기 전에 먼저 (위치 주위!!)
          //  dx 는 고정이기 때문에 dy 만 해주는 것 주의!!! // dx 도 같이 비교했다가 답 틀림
						ansMin = min(ansMin, minDp[dy][k]); 
						ansMax = max(ansMax, maxDp[dy][k]); 
						dy = parent[dy][k];
					}
				}
			}
			
			int lca = dx;
			
			if(dx != dy)
			{
				for(int k = max_level; k >= 0; k--)
				{
					if(parent[dx][k] != parent[dy][k])
					{
						ansMax = max(ansMax, max(maxDp[dx][k], maxDp[dy][k]));
						ansMin = min(ansMin, min(minDp[dx][k], minDp[dy][k]));
						dx = parent[dx][k];
						dy = parent[dy][k];
					}
					lca = parent[dx][k];
				}
			}
			if(dx != lca)
			{
				ansMin = min(ansMin, min(minDp[dx][0], minDp[dy][0]));
				ansMax = max(ansMax, max(maxDp[dx][0], maxDp[dy][0]));
			}
			bw.write(ansMin+" "+ansMax+"\n");
		}
		bw.flush();
	}
	public static void dfs(int cur, int p, int cost)
	{
		depth[cur] = depth[p] + 1;
		parent[cur][0] = p;
		
		maxDp[cur][0] = cost;
		minDp[cur][0] = cost;
		
		for(int i =1; i<= max_level; i++)
		{
			int temp = parent[cur][i-1];
			parent[cur][i] = parent[temp][i-1];
		}
		
		for(Node next : adj.get(cur))
		{
			if(next.dx != p)
			{
				dfs(next.dx, cur, next.cost);
			}
		}
	}
	public static void make_dp()
	{
		for(int jump = 1; jump <= max_level; jump++)
		{
			for(int cur =1; cur <= N; cur++)
			{
				int tmp = parent[cur][jump-1];
				maxDp[cur][jump] = max(maxDp[cur][jump-1], maxDp[tmp][jump-1]);
				minDp[cur][jump] = min(minDp[cur][jump-1], minDp[tmp][jump-1]);
			}
		}
	}
}

[WonYong-Jang]

LCA와 쿼리 (15480 )

• 쿼리마다 root 노드가 변경되는 문제!

일단 임의의 루트로 두고 lca를 구하는 sparse table을 만들어 놓고 r, u, v,에 대한 정답은

(r, u) / (r, v) / (u, v) 의 lca들의 depth들 중 가장 큰 값!!

LCA와 쿼리 2 ( 13511 )

• k 번째 수 구하는 구하기
• lca구하여 왼쪽과 오른쪽 높이를 각각 구한다.
• 만약 if(leftHeight >= k ) 라면 왼쪽에서 k번째를 찾고
• 그렇지 않은 경우 오른쪽에서 k 번째를 찾는데 이때 k- leftHeight 의 값을
• rightHeight 에 빼준 값을 k로 지정하여 sparse table 를 이용하여 노드를 찾는다.

leftDepth = depth[dx];
rightDepth = depth[dy];
lcaDepth = depth[lca];
leftHeight = leftDepth - lcaDepth + 1;
rightHeight = rightDepth - lcaDepth + 1;
int ans = 0, target =0, sum = 1;

if(leftHeight >= k) { // 왼쪽에서 k 번째 찾아 
target = dx;
}
else if(leftHeight < k) {
temp = k - leftHeight;
k = rightHeight - temp;
target = dy;
}