[백준] 단절선(11400) Java

문제 링크

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

11400번: 단절선

 

문제 요약

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

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

즉, 제거했을 때 그래프의 connected component의 개수가 증가하는 간선을 말한다.

 

입력

첫째 줄에 두 정수 V(1≤V≤100,000), E(1≤E≤1,000,000)가 주어진다.

이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다.

 

다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A, B가 주어진다.

이는 A번 정점과 B번 정점이 연결되어 있다는 의미이며, 방향은 양방향이다.

 

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

 

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

 

출력

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

 

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

 

접근법

기본적인 접근법은 단절점과 동일하다.

시작 node(방문하지 않은 node 중 하나를 선택하면 된다)부터 DFS로 그래프를 탐색하며, 방문한 node에 방문 순서를 기록한다.

order를 기록한 그래프

이 때 각 재귀에서 return하는 값을 low라고 하자. low가 의미하는 것은,

각 node에서 부모 node(DFS를 했을 때 자신을 재귀 호출한 바로 직전의 node)를 제외한 인접 node의 order중 가장 작은 order를 의미한다. 만약 해당 인접 node가 방문한적 없는 node(order가 0인 node)라면 해당 node로 다시 재귀호출을 해서 order를 기록하고, 반복적인 재귀호출을 통해 하위 node들의 low를 받아와서 넘겨준다.

방문한 적이 있는 node(order가 0이 아닌 node)라면 해당 node의 order를 넘겨준다.

 

이렇게 인접 node(와 그 하위 node)를 모두 탐색해서 얻어낸 low중 가장 작은 값을 상위 node로 넘겨준다.

 

이 때 low가 단절선을 찾는데 어떻게 사용되냐면,

만약 방문한 적 없는 인접 node A가 return하는 low값이 현재 node의 order보다 크다면, 현재 node에서 node A를 거쳐서 현재 노드로 다시 돌아올 수 있는 방법이 존재하지 않는다는 의미이다. 즉 현재 node에서 A로 향하는 간선을 끊으면 connected graph의 수가 늘어난다는 것이다.

 

low값이 현재 node의 order보다 작거나 같으면 어떤 방식으로든 다시 돌아올 수 있는 길이 있으므로 해당 간선을 끊어도 그래프가 끊어지지 않는다.

 

여기서 단절점과 다른 부분은, 시작 node를 따로 처리해줄 필요가 없다는 것이다.

단절점에서는 시작 node의 방문하지 않은 자식이 1개인 경우 해당 node를 제거해도 connected graph의 수가 늘어나지 않는데, 단절선의 경우 자식 node가 1개인 시작 node에서 간선을 끊으면 connected graph의 수가 늘어나기 때문이다.

 

따라서 오히려 단절선 문제가 더 쉽다고 볼 수도 있다.

 

 

시간 복잡도

DFS로 전체 그래프를 한번만 탐색하면 된다.

이 때 각 node에서 모든 edge를 다 확인하므로 O(V+E) 이다.

 

 

공간 복잡도

그래프를 표현하기 위해 V 크기의 2차원 ArrayList에, 2E 크기의 ArrayList<Integer>가 사용된다.

추가로 V 크기의 visited 배열이 사용된다.

V와 E가 큰 편이 아니므로 문제 푸는데 지장은 없다.

 

풀면서 놓쳤던 점

출력이 사전순이라는 부분을 놓쳐서 계속 실패했다.

또 Scanner를 썼더니 시간초과가 났다.

 

 

이 문제에서 얻어갈 점

단절점과 단절선의 차이.

사전순 출력을 위해 comparable을 구현하는 법.

 

 

코드

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

public class Main
{
	static int V, E;

	//graph를 표현하기 위한 2차원 ArrayList
	static ArrayList<ArrayList<Integer>> nodes;

	//각 node의 방문 순서를 의미하는 order. 그 order를 기록할 visited 배열
	static int order;
	static int[] visited;

	//정답을 기록할 PriorityQueue. 사전순으로 출력해야하므로 PriorityQueue 사용.
	static PriorityQueue<Bridge> bridges;

	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;

		//V와 E 입력
		st = new StringTokenizer(br.readLine());
		V = Integer.parseInt(st.nextToken());
		E = Integer.parseInt(st.nextToken());

		nodes = new ArrayList<ArrayList<Integer>>(V + 1);
		for (int i = 0; i <= V; i++)
			nodes.add(new ArrayList<Integer>());

		//그래프 입력. 양방향 간선임에 주의.
		int node1, node2;
		for (int i = 0; i < E; i++)
		{
			st = new StringTokenizer(br.readLine());
			node1 = Integer.parseInt(st.nextToken());
			node2 = Integer.parseInt(st.nextToken());

			nodes.get(node1).add(node2);
			nodes.get(node2).add(node1);
		}

		//order는 1부터 시작함.
		order = 1;
		visited = new int[V + 1];
		bridges = new PriorityQueue<Bridge>();

		//입력 조건에서 connected graph라는 조건이 있으므로 한 번만 호출하면 됨.
		//시작 node는 부모가 없으므로 의미 없는 node id인 0 을 넘겨줌.
		check_bridge(1, 0);

		StringBuilder sb = new StringBuilder();
		Bridge b = null;

		//정답을 사전순으로 출력.
		sb.append(bridges.size() + "\n");
		while (!bridges.isEmpty())
		{
			b = bridges.poll();
			sb.append(b.node1 + " " + b.node2 + "\n");
		}

		bw.write(sb.toString());

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

	static int check_bridge(int id, int parent)
	{
		int low, subtree_low;

		//order를 기록함. return할 low의 초깃값은 order임.
		visited[id] = order;
		low = order;
		order++;

		for (int adj : nodes.get(id))
		{
			//부모 노드로 다시 올라가지 않음.
			if (adj == parent)
				continue;

			//방문한 적이 없는 인접 node인 경우 재귀 호출.
			if (visited[adj] == 0)
			{
				//재귀 호출 후 반환받은 값으로 low 갱신.
				subtree_low = check_bridge(adj, id);
				low = Math.min(low, subtree_low);

				//다시 돌아올 방법이 없는 경우에 bridge
				if (visited[id] < subtree_low)
					bridges.add(new Bridge(id, adj));
			}
			//방문한 적이 있는 node인 경우, 돌아갈 방법이 있다는 것이므로 bridge인 것을 고려할 필요가 없음.
			//low만 갱신해준다.
			else
				low = Math.min(low, visited[adj]);
		}

		return low;
	}
}

class Bridge implements Comparable<Bridge>
{
	int node1;
	int node2;

	public Bridge(int node1, int node2)
	{
		//출력 조건에 있는 A < B 를 맞춰주기 위함
		if (node1 > node2)
		{
			this.node1 = node2;
			this.node2 = node1;
		}
		else
		{
			this.node1 = node1;
			this.node2 = node2;
		}
	}

	//출력 조건에 있는 사전순 출력을 맞추기 위해 구현.
	public int compareTo(Bridge other)
	{
		if (this.node1 > other.node1)
			return 1;
		else if (this.node1 == other.node1)
			return this.node2 - other.node2;
		else
			return -1;
	}
}