[BOJ] 11266 단절점 Java 풀이

 

 

BOJ 11266 단절점

 

문제는 간단하지만 해결은 좀처럼 쉽지 않다. 다만 DFS 응용으로 다소 중요하게 다뤄지는 개념이다. 단절점이나 단절선 문제 유형에 대해서 잘 익히고 가야겠다. 

문제 해결에 있어 중점적인 부분은 최소 방문 순서를 기록하고 비교하는 것이다.

노드를 방문할 때마다 방문 순서를 매기고, 연결된 노드들의 방문 순서를 비교해가며 연결된 노드들의 최소 방문 순서를 구하고, 현재 노드의 최소 방문 순서를 비교해 현재 노드의 최소 방문 순서보다 연결된 노드과 재귀적으로 연결된 노드들의 최소 방문 순서가 같거나 크면, 현재 노드를 단절점으로 구별하는 것이다.

예를 들어, 예제 그래프는 아니지만 위와 같은 그래프가 있다고 하면, 1번 노드에서 부터 깊이 우선 탐색 방법으로 탐색을 시작하면서, 방문 순서를 기록해보면 [1, 2, 3, 4, 5] 순으로 방문하게 된다. (편의상 반복문을 1 ~ N 순으로 코드를 짜는 경우)

1번 노드에서는 연결된 간선이 하나이므로 2번을 방문하고 나면 3, 4번 노드로 이동할 수 있지만 DFS 탐색이므로 3번을 방문했다가, 4번 노드를 방문한다. 2번 노드에서는 3, 4번 노드와 연결된 노드의 최소 방문 순서를 비교하려하는데, 3번 노드는 다시 연결된 4, 5번노드의 최소 방문 순서를 찾기 위해 4번 노드를 방문한다. 4번 노드는 다시 2번 노드와 연결되어있으므로 4번 노드와 연결된 노드의 최소 방문 순서는 2이고, 3번도 3번과 연결된 노드의 최소 방문 순서를 2로 update한다. 다시 2번 노드는 3, 4번 노드와 연결된 최소 방문 순서가 자신과 같은 2이므로 단절점임을 알 수 있다.

이 과정을 살펴보면 자신과 연결된 노드의 최소 방문 순서가 같은 경우는 자신부터 시작하는 cycle을 형성하는 경우임을 알 수 있다. 또, 맨 오른쪽 그림에서 3번 노드의 경우 자신과 cycle을 형성하는 2, 4번 노드를 제외하고 5번 노드의 경우 leaf 노드이면서 최소 방문 순서가 반드시 자신보다 크다. 자신과 연결된 노드의 최소 방문 순서가 자신보다 더 큰 경우는 자신을 제외하면 연결되지 않는 관계임을 알 수 있다.

이와 같은 로직이 이 문제에서의 핵심 풀이 방법인데, 이에 더해 몇 가지 예외 처리가 더 필요하다.
1) leaf node는 제거하면 connected component 개수가 증가하지 않으므로 이에 대한 처리
2) 탐색을 시작한 노드(root)가 edge를 2개 이상 가지고 있으면 단절점으로 인식해주는 처리
(탐색 과정에서 무한 루프를 돌게하지 않기 위해 자신을 호출한 노드는 다시 올라가지 않도록 처리하는데, 여기서 오류 발생)
3) 입력받은 전체 그래프에서 connected component 개수가 1개가 아닌 경우 처리

이를 모두 고려해 코드를 작성하면 AC를 받을 수 있다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
	static int V, E;
	static int visit_order[];
	static ArrayList<Integer> adj[];
	static boolean ans[];	// 단절점 여부 기록
	static int ansCnt;		// 단절점 개수
	static int num;			// 방문 순서
	

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		V = Integer.parseInt(st.nextToken());
		E = Integer.parseInt(st.nextToken());
		
		adj = new ArrayList[V + 1];
		visit_order = new int[V + 1];
		ans = new boolean[V + 1];
		
		for(int i = 0; i <= V; i++) {
			adj[i] = new ArrayList<>();
		}
		
		for(int i = 0; i < E; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			
			adj[a].add(b);
			adj[b].add(a);
		}
		
		// DFS로 단절점 찾기
		for(int i = 1; i <= V; i++) {
			// 그래프가 모두 연결되어 있는 상태가 아니기 때문에...
			if(visit_order[i] == 0) {
				// 시작하는 점을 root
				dfs(0, i, true);
			}
		}
		
		// 단절점 개수 count 
		for(int i = 1; i <= V; i++) {
			if(ans[i]) ansCnt++; 
		}
		System.out.println(ansCnt);
		
		for(int i = 1; i <= V; i++) {
			if(ans[i]) {
				System.out.print(i + " ");
			}
		}
		
	} // end of main
	
	private static int dfs(int parent, int cur, boolean isRoot) {
		// 1. check in
		
		// 현재 노드 방문한 적 없는 경우에만 실행
		if(visit_order[cur] != 0) return 0;
		int min_visit_order = 10010;	// 자식 노드들 중 가장 작은 방문 순서
		int chlcnt = 0;		// 자식 노드 개수
		
		// 방문 순서 입력
		num++;
		visit_order[cur] = num;
		
		// 2. (목적지에 도착했는가?)
		
		
		// 3. 연결된 곳 순회
		for(int i = 0; i < adj[cur].size(); i++) {
			int nxt = adj[cur].get(i);
			
			// 4. 갈 수 있는가
			// 간선이 부모 노드와의 간선이면 건너뜀
			if(nxt == parent) continue;		
			
			// 연결된 노드가 방문한 적이 있고,
			if(visit_order[nxt] != 0) {
				// 현재 노드보다 일찍 방문했다면 자식 중 최소 방문 순서를 update
				if(visit_order[nxt] < min_visit_order) {
					min_visit_order = visit_order[nxt];
				}
			}else {	// 연결된 노드가 방문한 적 없는 경우에만 방문
				 
				// 5. 간다
				int tmp = dfs(cur, nxt, false);
				min_visit_order = Math.min(min_visit_order, tmp);
				
				if(isRoot != true && tmp >= visit_order[cur]) {
					// 루트노드가 아니고,
					// 연결된 점의 주변 최소 방문 순서가 현재 점보다 같거나 크면 현재 점은 단절점!
					ans[cur] = true;
				}
				chlcnt++;
			}
		}
		
		// 리프노드면 단절점 처리 해주지 않음
		if(adj[cur].size() == 1) {
			return visit_order[cur];
		}
		
		// root 노드 예외 처리
		if(isRoot) {
			if(chlcnt >= 2) {
				ans[cur] = true;
			}
		}
		
		// 체크아웃
		return Math.min(min_visit_order, visit_order[cur]);
	}

}