백준 3176번(JAVA)

 

백준 문제중 11438번 LCA2가 있는데, 트리를 타고 올라갈때 한 칸 씩 올라가는게 아니라 2의N승씩 올라가는 빠른 LCA가 있다. 밑에 문제를 풀 줄 안다면 이번 3176번도 손 쉽게 풀 수있다. 

https://www.acmicpc.net/problem/3176

3176번: 도로 네트워크

빠른 LCA탐색 문제는 부모를 2의N승 부모를 저장한다. 예를들어 

위 그림과 같은 트리가 있다고 가정해보자. 

기존에는 바로 위의 부모만 저장했다. 그래서 공통조상을 찾을때에도 한칸씩 한칸씩 올라갔다. 

하지만 이번 문제에서도 그렇게 구현하면 테스트케이스를 통과해도 무조건 시간초과가 나온다. 

그렇기에 int[][] parent 이렇게 2차원배열을 구현해준다.

위 그림으로 설명하자면

• 8의 2의0승부모(바로 1칸 위 부모)는 7이다
• 8의 2의1승 부모(2칸 위 부모)는 5다
• 8의 2의2승 부모(4칸 위 부모)는 15다

이거를 어떻게 저장하느냐?

• parent[0][8]=7
• parent[1][8]=5
• parent[2][8]=15

여기에 추가로 이번 문제는 int[][] Max,int[][] Min 이렇게 2차원 배열 2개를 만들어어서 2의 몇승 부모까지 가는 길중에 가장 긴 도로 짧은 도로도 다 구해주자.

for(int i=1;i<=LogN;i++)//각 노드상대로 2의 몇승부모는 누구인지, 2의 몇승부모까지의 가장 긴 도로 가장 짧은 도로 구하기
		{
			for(int j=1;j<=N;j++)
			{
				parent[i][j]=parent[i-1][parent[i-1][j]];
				Max[i][j]=Math.max(Max[i-1][j], Max[i-1][parent[i-1][j]]);
				Min[i][j]=Math.min(Min[i-1][j], Min[i-1][parent[i-1][j]]);
			}
		}

개인적으로 생각하는 이 문제에서 가장 중요한 부분이라고 생각한다.

BFS로 각 노드의 1칸위 부모와 가중치를 parent,Max,Min 배열들에 저장해준다. 

그리고 for문을 돌면서 각 노드의 2의N승부모와 2의N승 부모까지의 가장 긴 도로, 가장 짧은 도로들을 다 저장해준다.

 

나머지 설명은 주석을 보면서 이해하길 바란다.

전체코드

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

class Node
{
	int V;
	int W;
	public Node(int V,int W)
	{
		this.V=V;
		this.W=W;
	}
}
public class Main {

	public static int[][] parent;//2의 몇승 부모를 저장할 예정
	public static int[][] Max;//2의 몇승 부모까지의 가장 긴 도로
	public static int[][] Min;//2의 몇승 부모까지의 가장 짧은 도로
	public static int[] Depth;//깊이 저장
	public static boolean[] visited;
	public static ArrayList<Node>[] tree;
	public static int LogN=17;
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		int N=Integer.parseInt(br.readLine());
		Depth=new int[N+1];
		visited=new boolean[N+1];
		parent=new int[18][N+1];
		Max=new int[18][N+1];
		Min=new int[18][N+1];
		String[] s;
		tree=new ArrayList[N+1];
		for(int i=1;i<=N;i++)
		{
			tree[i]=new ArrayList<Node>();
		}
		for(int i=0;i<N-1;i++)
		{
			s=br.readLine().split(" ");
			int A=Integer.parseInt(s[0]);
			int B=Integer.parseInt(s[1]);
			int W=Integer.parseInt(s[2]);	
			tree[A].add(new Node(B,W));
			tree[B].add(new Node(A,W));
		}
		BFS();//트리 형성
		for(int i=1;i<=LogN;i++)//각 노드상대로 2의 몇승부모는 누구인지, 2의 몇승부모까지의 가장 긴 도로 가장 짧은 도로 구하기
		{
			for(int j=1;j<=N;j++)
			{
				parent[i][j]=parent[i-1][parent[i-1][j]];
				Max[i][j]=Math.max(Max[i-1][j], Max[i-1][parent[i-1][j]]);
				Min[i][j]=Math.min(Min[i-1][j], Min[i-1][parent[i-1][j]]);
			}
		}
		int K=Integer.parseInt(br.readLine());
		StringBuilder sb=new StringBuilder();
		for(int i=0;i<K;i++)
		{
			s=br.readLine().split(" ");
			int a=Integer.parseInt(s[0]);
			int b=Integer.parseInt(s[1]);
			if(Depth[a]>Depth[b])
			{
				LCA(b,a);//첫 번째 인수가 깊이가 더 낮게(더 작게) 구현
			}
			else
			{
				LCA(a,b);
			}
			
		}
	}
	public static void BFS()//깊이 및 부모 저장, 1번을 루트 노드로 잡을 것이다
	{
		Depth[1]=0;//높이는 0부터
		Queue<Integer> q=new LinkedList<Integer>();
		q.add(1);
		while(!q.isEmpty())
		{
			int now=q.poll();
			if(visited[now])//방문된적이 있다면
			{
				continue;
			}
			visited[now]=true;//방문 처리
			for(Node nextNode:tree[now])
			{
				int next=nextNode.V;
				if(visited[next])//부모로 다시 역행하는걸 막아준다
				{
					continue;
				}
				Depth[next]=Depth[now]+1;
				parent[0][next]=now;
				Min[0][next]=nextNode.W;
				Max[0][next]=nextNode.W;
				q.add(next);
			}
		}
	}
	public static int log(int N)//LCA함수에서 몇칸 올라갸야 되는지 계산
	{
		int temp=0;
		while(Math.pow(2, temp)<=N)
		{
			temp++;
		}
		return temp-1;
	}
	public static void LCA(int a,int b)//b의 깊이가 더 깊게 구현
	{
		int max_result=Integer.MIN_VALUE;
		int min_result=Integer.MAX_VALUE;
		while(Depth[a]!=Depth[b])//둘의 깊이가 다르다면 맞춰준다, 이것도 2의 N승으로 올라가주자
		{
			int temp=Depth[b]-Depth[a];
			max_result=Math.max(max_result, Max[log(temp)][b]);
			min_result=Math.min(min_result, Min[log(temp)][b]);
			b=parent[log(temp)][b];
		}
		if(a==b)//높이를 맞춰줬는데 만약 똑같은 수라면, 그냥 이대로 결과 출력하고 끝낸다.
		{
			System.out.println(min_result+" "+max_result);
			return ;
		}
		for(int i=17;i>=0;i--)
		{
			if(parent[i][a]!=parent[i][b])
			{
				max_result=Three_Max(Max[i][a], Max[i][b],max_result);
				min_result=Three_Min(Min[i][a],Min[i][b],min_result);
				a=parent[i][a];
				b=parent[i][b];
			}
		}
		max_result=Three_Max(Max[0][a], Max[0][b],max_result);
		min_result=Three_Min(Min[0][a],Min[0][b],min_result);//모든 절차가 끝나면 
		System.out.println(min_result+" "+max_result);
	}
	public static int Three_Max(int a,int b,int c)//세 숫자중 가장 큰 숫자 반환
	{
		if(a>=b&&a>=c)
		{
			return a;
		}
		else if(b>=a&&b>=c)
		{
			return b;
		}
		else
		{
			return c;
		}
	}
	public static int Three_Min(int a,int b,int c)//세 숫자중 가장 작은 숫자 반환
	{
		if(a<=b&&a<=c)
		{
			return a;
		}
		else if(b<=a&&b<=c)
		{
			return b;
		}
		else 
		{
			return c;
		}
	}
}

p.s

사실 설명이 틀린 부분이 있을수도 있으니 이 포스팅만 너무 믿진 말고 다른 블로그도 참고해보시길....