Algorithms
[BOJ] 11266 단절점 Java 풀이
문제는 간단하지만 해결은 좀처럼 쉽지 않다. 다만 DFS 응용으로 다소 중요하게 다뤄지는 개념이다. 단절점이나 단절선 문제 유형에 대해서 잘 익히고 가야겠다. 문제 해결에 있어 중점적인 부분은 최소 방문 순서를 기록하고 비교하는 것이다. 노드를 방문할 때마다 방문 순서를 매기고, 연결된 노드들의 방문 순서를 비교해가며 연결된 노드들의 최소 방문 순서를 구하고, 현재 노드의 최소 방문 순서를 비교해 현재 노드의 최소 방문 순서보다 연결된 노드과 재귀적으로 연결된 노드들의 최소 방문 순서가 같거나 크면, 현재 노드를 단절점으로 구별하는 것이다. 예를 들어, 예제 그래프는 아니지만 위와 같은 그래프가 있다고 하면, 1번 노드에서 부터 깊이 우선 탐색 방법으로 탐색을 시작하면서, 방문 순서를 기록해보면 [1, ..
2021. 3. 4.
