[BOJ 백준] 단절선(11400) Java

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

 

문제 설명 : 

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

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

입력 :

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

그래프는 항상 연결되어 있으며, 같은 간선이 두 번 이상 들어오는 경우는 없다. 또, A와 B가 같은 경우도 없다.

그래프의 정점은 1부터 V까지 자연수이다.

출력 :

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

둘째 줄부터 K개 줄에는 단절선을 사전순으로 한 줄에 하나씩 출력한다. 간선은 "A B" 형식으로 출력해야 하고, A < B를 만족해야 한다. 같은 간선은 한 번만 출력하면 된다. 즉, "A B"를 출력한 경우에 "B A"는 출력할 필요가 없다.

예제 입력 :

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

예제 출력 :

2
1 6
6 7

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

 

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

 

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

 

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

 

 

에서 ① - ⑥, ⑥ - ⑦ 을 연결하는 간선이 없어질때 그래프가 2개 이상으로 나뉘어져 단절선 이라고 할 수 있다.

 

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

단절점과 유사한 부분이 많다.

단절점을 먼저 공부해보는 것을 추천한다. https://subbak2.tistory.com/58

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

 

 

단절선은 단절점과 달리 root node를 고려할 필요가 없다. 

그래서 어떻게 보면 더 단순하다.

 

1) DFS를 활용해 방문순서를 visit 배열에 기록하고

2-1) 자식을 최초 방문했을 경우 → 역전이 불가능하면 단절점

2-2) 자식을 이미 방문한 경우 visit[자식]과 현재 ret값 비교

만 하면 된다.

 

자세한 코드는 아래 참고.

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

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

(Java 기준 - 936ms)

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

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

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

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

Java 코드 : 

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

// 11400 단절선
public class Main { 
	
	static int V, E;	// V : 정점 수, E : 간선 수
	static int A, B;    // 입력 변수
	static int order; 	// 단절선 DFS용 순서 기록 변수저
	
	static ArrayList[] adjList;		// 인접리스트
	static int[] visited;				// 단절선 DFS용 방문 순서 배열
	
	static PriorityQueue<edge> ansList;	// 정답 간선 리스트

	static class edge implements Comparable<edge>{
		int startId, targetId;

		public edge(int startId, int targetId) {
			this.startId = startId;
			this.targetId = targetId;
		}

		@Override		// 사전순 출력
		public int compareTo(edge o) {
			if (this.startId > o.startId) {
				return 1;
			}
			if (this.startId == o.startId) {
				return this.targetId - o.targetId;
			}
			return -1;
		}
	}
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;

		// 1. 입력 & 변수 준비
		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>();
		}
		
		for (int i = 1; i<= E; i++) {
			st = new StringTokenizer(br.readLine());
			A = Integer.parseInt(st.nextToken());
			B = Integer.parseInt(st.nextToken());
		
			adjList[A].add(B);
			adjList[B].add(A);
		}

		visited = new int[V+1];
		order = 1;
		// 2. 모든 정점 돌면서 단절선 체크하고 정답배열에 추가
		ansList = new PriorityQueue<edge>();
		for (int i = 1; i<=V; i++) {
			if (visited[i]==0) {
				dfs(i, 0);
			}
		}

		// 3. 출력
		StringBuilder sb = new StringBuilder ();
		int len = ansList.size();
		sb.append(len+"\n");
		
		while(!ansList.isEmpty()) {
			edge cur = ansList.poll();
			sb.append(cur.startId+" "+cur.targetId+"\n");
		}
		bw.write(sb.toString());

		bw.flush();
		bw.close();
		br.close();
	}

	static int dfs(int id, int parent) {
		// 1. 방문순서 기록 후 자식(child)과 비교 준비
		visited[id] = order;
		order++;
		int ret = visited[id];
		
		// 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) {

				// 자식 정점 중 방문순서가 빠른 값 
				int low = dfs(next, id);
				
				// ★★★★★ 역전이 불가능한 경우 단절선.
				if (low > visited[id]) {
					// edge 출발점이 더 작은 수로 바꿔서 정답배열에 추가 (문제 출력 요구사항) 
					if (next > id) {
						ansList.add(new edge(id, next));
					}
					else {
						ansList.add(new edge(next, id));
					}
				}
				ret = Math.min(ret, low);
			}
			// 2-2. 자식을 이미 방문한 경우
			//      사이클이 있는 경우
			else {
				ret = Math.min(ret,  visited[next]);
			}
		}
		return ret;
	}
}