백준 11266번 단절점 java 풀이

문제

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

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

입력

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

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

출력

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

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

예제 입력 1 복사

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

예제 출력 1 복사

3
1 6 7

 

 

역시 플레문제는 너무 어렵다.. 어렵고도 어렵다.....

그래도 이렇게 풀어보면서 DFS에 대한 이해도가 한층 더 높아진듯하다..

그래도 너무 어렵다.. 진짜 어렵다...... 더 잘 풀고싶다...

 

문제 로직

DFS 스패닝트리, DST를 이용한 문제이다.

DFS 방문순서를 각 노드에 저장을 하고 각 노드들을 방문해서 만약에 연결되어 있는 모든 노드들의 방문 가능한 노드들이 가지고 있는 방문순서의 최소값을 계속해서 갱신하고 만약에 현재 노드의 방문순서보다 최소 방문순서의 값이 더 크거나 같다면 그 지점은 단절점이다. 왜냐하면 현재 dfs를 통해서 현재 노드와 연결된 노드들에게서 가져온 최소 방문순서가 현재 노드의 방문순서보다 더 크다는뜻은  현재 노드를 거치지 않고는 다른 노드로 갈 수 없다는 뜻이기 때문에 단절점이 된다.

 

알고리즘을 풀어보면 알겠지만 정말 귀찮은 수작업을 직접 진행하고 표로 남겨주신 블로그 설명 덕분에 겨우 이해를 할 수 있었다. 해당 블로그를 첨부한다.

https://ip99202.github.io/posts/%EB%8B%A8%EC%A0%88%EC%A0%90-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98/

단절점 알고리즘

 

- 코드 생략