[BOJ 백준] 단절점(11266) Java

링크 : https://www.acmicpc.net/problem/11266

문제 설명 : 

그래프가 주어졌을 때, 단절점을 모두 구해 출력하는 프로그램을 작성하시오.

단절점이란 그 정점을 제거했을 때, 그래프가 두 개 또는 그 이상으로 나누어지는 정점을 말한다. 즉, 제거했을 때 그래프의 connected component의 개수가 증가하는 정점을 말한다.

입력 :

첫째 줄에 두 정수 V(1≤V≤10,000), E(1≤E≤100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A, B가 주어진다. 이는 A번 정점과 B번 정점이 연결되어 있다는 의미이며, 방향은 양방향이다.

입력으로 주어지는 그래프는 연결 그래프가 아닐 수도 있다. 정점은 1부터 V까지 번호가 매겨져 있다.

출력 :

첫째 줄에 단절점의 개수를 출력한다.

둘째 줄에는 단절점의 번호를 공백으로 구분해 오름차순으로 출력한다.

예제 입력 :

7 7
1 4
4 5
5 1
1 6
6 7
2 7
7 3

예제 출력 :

3

1 6 7

접근법 :
1) 어떻게 풀 것인가?
문제 제목, 첫 줄 내용부터 특정 알고리즘을 물어보기로 작정한 문제이다.

 

"그래프가 주어졌을 때, 단절점을 모두 구해 출력하는 프로그램을 작성하시오."

 

단절점 알고리즘을 구현하면 되는 문제이다.

 

문제에서 주어진 예제를 통해 살펴보면

 

① 최초 정점, 간선의 관계

 

에서 ①, ⑥, ⑦ 정점은 없어진다면, 그래프가 2개 이상으로 나뉘어져 단절점 이라고 할 수 있다.

 

② 단절점들이 없어진다면 → 2개 이상으로 서로 분리

 

단절점은 DFS를 활용해서 구하는데, 

1. 루트 노드의 경우 자식이 2개 이상이면 단절점

2. 루트 노드가 아닌 경우, 자식이 갈 수 있는 최소 방문 순서가 내 방문 순서보다 크다면  단절점이 된다.

 

루트 노드인 경우는 이해하기 쉬운데,

루트 노드가 아닌 경우는 그림을 통해 이해하는게 편하다.

 

DFS로 위와 같이 각 정점의 방문 순서를 배열에 기록을 한다고 했을때, 

 

* ⑥ 노드의 경우  - 단절점인 경우

  - ① 의 자식이다 (방문순서가 1 다음이므로)

  - ⑥의 자식들 (⑦, ②, ③)과 연결된 가장 빠른 방문순서 '5'가 ⑥의 방문순서 '4'보다 앞서지 않으므로 단절점이다.

      ( 우회 경로가 없다는 의미)

 

* ④ 노드의 경우 - 단절점이 아닌 경우

 - ① 1의 자식이다 (방문순서가 1 다음이므로)

 - ④의 자식 ⑤와 연결된 ①의 방문순서 '1'이 ④의 방문순서 '2'보다 앞서므로 단절점이 아니다.

   (우회 경로가 존재한다)

 

따라서, 2. 루트 노드가 아닌 경우, 자식이 갈 수 있는 최소 방문 순서가 내 방문 순서보다 크다면  단절점이 된다.

 

자세한 코드는 아래 내용 참고.

단절선을 묻는 경우도 있는데 DFS를 응용해서 방문순서의 역전 여부를 확인하는 로직은 완전히 동일하다.

2) 시간복잡도
방문한 정점은 다시 방문하지 않는 경우 

V개의 정점에서 DFS를 실행하며, 연결된 Edge를 모두 확인하므로 O(V+E)로 양호하다.

(Java 기준 - 536ms)

3) 공간복잡도
간선의 개수가 10만개로 양호함.

100,000 * 4(int = 4Bytes) = 1MB 미만

4) 풀면서 놓쳤던점
특별히 없음.

5) 이 문제를 통해 얻어갈 것
단절점 기본 코드 작성법.

Java 코드 : 

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

// 11266 단절점
public class Main {
	
	static int V,E, order, ans;
	static ArrayList[] adjList;
	static int[] visited;
	static boolean[] isDjj;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader (new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter (new OutputStreamWriter(System.out));
		
		// 1. 입력
		StringTokenizer st = new StringTokenizer(br.readLine());
		V = Integer.parseInt(st.nextToken());
		E = Integer.parseInt(st.nextToken());
		
		adjList = new ArrayList[V + 1];
		for (int i = 1; i <= V; i++) {
			adjList[i] = new ArrayList<Integer>();
		}
		
		// 양방향 간선 
		int startId, targetId;
		for (int i = 1; i<=E; i++) {
			st = new StringTokenizer(br.readLine());
			startId = Integer.parseInt(st.nextToken());
			targetId = Integer.parseInt(st.nextToken());
			
			adjList[startId].add(targetId);
			adjList[targetId].add(startId);
		}

		// 2. visit 배열, 단절점 여부 초기화 후 V 모두 DFS
		visited = new int [V+1];
		isDjj = new boolean [V+1];
		
		// order는 전역변수
		order = 1;
		for (int i=1; i<=V; i++) {
			if (visited[i] == 0) {
				// id,  parentId,  isRoot
				dfs(i, 0, true);
			}
		}
		
		// 3. 단절점 개수 count 및 출력
		ans = 0;
		StringBuilder sb = new StringBuilder ();
		for (int i=1; i<=V; i++) {
			if (isDjj[i]) {
				ans++;
				sb.append(i+" ");
			}
		}
		
		bw.write(ans+"\n"+sb);
		
		bw.flush();
		bw.close();
		br.close();
	}
	
	static int dfs(int id, int parent, boolean isRoot) {

		// 1. 방문 순서 기록 후 자식(child)과 비교 준비
		visited[id] = order;
		order++;
		
		// ret : 함수가 return하면서 방문했던 최소 order를 리턴
		//       역전 현상이 발생하는지 확인하는 용도
		int ret = visited[id];
		int childCnt = 0;
		
		// 2. 자식 DFS - 인접 정점을 모두 확인
		int len = adjList[id].size();
		for (int i = 0; i < len; i++) {
			int next = (int) adjList[id].get(i);
			
			// 왔던길 돌아가기 방지
			if (next == parent) continue;
			
			// 2-1. 자식 최초 방문했을 경우
			if (visited[next]==0) {
				childCnt++;
				
				// 자식 정점 중 방문순서가 빠른 값 
				int lowOrder = dfs(next, id, false);
				
				// Root 가 아니고, order 역전이 불가능하면 단절점
				if (!isRoot && lowOrder >= visited[id]) {
					isDjj[id] = true;
				}
				ret = Math.min(ret, lowOrder);
			}
			// 2-2. 자식을 이미 방문한 경우 
			else {
				ret = Math.min(ret, visited[next]);
			}
		}
		
		// 3. 루트 정점인 경우 자식 개수가 2개 이상이면 단절점
		if (isRoot && childCnt >= 2) {
			isDjj[id] = true;
		}
		return ret;
	}
}