[BOJ] 백준 20530번 양분 (Java)

#20530 양분

난이도 : 골드 2

유형 : 트리 / DFS

20530번: 양분

▸ 문제

나무 T는 양분을 먹고 자란다.

원래 나무는 정점 N개와 간선 N−1개로 구성되어야 하지만, 양분을 너무 많이 먹어버린 나머지 나무 T는 N개의 간선을 갖게 되었다. 더 이상 트리가 아니기 때문에 T는 꿈의 무대인 트리와 쿼리에 등장하지 못한다. 슬퍼하고 있는 T 위해 정휘는 새로운 문제를 만들어 주었다.

 N개의 정점과 N개의 간선으로 이루어진 연결 그래프 T가 주어진다. 정점은 1번부터 N번까지 번호가 매겨져 있고, 간선도 1번부터 N번까지 번호가 매겨져 있다. 아래 쿼리를 수행하는 프로그램을 작성하시오.

•  u v : u번 정점에서 v번 정점으로 가는 단순 경로의 수를 출력한다.

▸ 입력

첫째 줄에 두 자연수 N, Q가 주어진다. 주어지는 그래프의 정점과 간선의 개수가 N개이며 쿼리가 Q개 주어진다는 것을 의미한다.

둘째 줄부터 N개의 줄에는 i번 간선이 연결하는 두 정점 번호 a, b가 주어진다.

다음 Q개 줄에는 쿼리가 한 줄에 하나씩 주어진다.

▸ 출력

각각의 쿼리마다 한 줄에 하나씩 결과를 출력한다.

문제 풀이  

문제 풀이 과정은 2가지로 나뉜다. 첫 번째는 싸이클이 된 영역 찾기이고 두 번째는 싸이클을 제외한 부분을 그룹화시키기이다.

 

첫 번째 싸이클이 된 영역을 찾는 것은 DFS로 풀이를 할 수 있다.

• !vistied[nxt] 방문여부를 체크하며 방문하지 않은 곳을 DFS 탐색을 한다.
• !finished[nxt] && nxt != pa 해당 노드의 탐색이 종료되지 않는 시점에 방문했던 곳을 재방문할 경우 싸이클로 간주한다.
• checkCycle 싸이클로 된 영역을 표시해준다.

 

두 번째로 그룹화시키는 부분 또한 DFS로 풀이할 수 있다.

• 1 ~ n 번의 노드를 순차대로 DFS 탐색을 한다. 탐색 시작 조건은 이전에 방문하지 않고 싸이클 영역에 속해있어야 한다.
• 싸이클 영역에 해당하는 노드를 그룹의 대표로 싸이클에 해당하지 않은 영역을 그룹화시켜주면 된다.

 

이젠 이렇게 구한 값으로 답을 구해주면 된다.

• 같은 그룹에 속해있을 경우 연결하는 경로는 1개이다.
• 다른 그룹에 속해있을 경우 연결하는 경로는 2개이다.

풀이 코드 

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

public class Main {

	static List<Integer>[] list;
	static int[] parent, group;	
	static boolean[] isCycle, visited, finished;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int n = Integer.parseInt(st.nextToken());
		int q = Integer.parseInt(st.nextToken());
		
		list = new ArrayList[n+1];
		for(int i=1; i<=n; i++) {
			list[i] = new ArrayList<>();
		}
		
		isCycle = new boolean[n+1];
		visited = new boolean[n+1];
		finished = new boolean[n+1];
		parent = new int[n+1];
		for(int i=0; i<n; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			list[a].add(b);
			list[b].add(a);
		}
		
		// cycle 찾기
		findCycle(1, 0);
		
		// 그룹화 시키기
		group = new int[n+1];
		Arrays.fill(visited, false);
		for(int i=1; i<=n; i++) {
			if(!visited[i] && isCycle[i]) {
				grouping(i,i);	
			}
		}
		
		StringBuilder sb = new StringBuilder();
		for(int i=0; i<q; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			if(group[a] == group[b]) {
				sb.append(1);
			}else {
				sb.append(2);
			}
			sb.append("\n");
		}
		System.out.println(sb.toString());
	}
	
	static void grouping(int here, int g) {
		visited[here] = true;
		group[here] = g;
		for(int nxt : list[here]) {
			if(isCycle[nxt] || visited[nxt]) continue;
			grouping(nxt, g);
		}
	}
	
	static void findCycle(int here, int pa) {
		visited[here] = true;
		for(int nxt : list[here]) {
			if(!visited[nxt]) {
				parent[nxt] = here;
				findCycle(nxt, here);
			} else if(!finished[nxt] && nxt != pa) {
				checkCycle(here, nxt);
			}
		}
		finished[here] = true;
	}
	
	static void checkCycle(int here, int root) {
		isCycle[here] = true;
		if(here == root) return;
		checkCycle(parent[here], root);
		
	}	
}