Graph 썸네일형 리스트형 [DFS] 그래프 단절점, 단절선 그래프의 단절점과 단절선이란? 단절점: 단절점이란 그 정점을 제거했을 때, 그래프가 두 개 또는 그 이상으로 나누어지는 정점을 말한다. 즉, 제거했을 때 그래프의 connected component의 개수가 증가하는 정점을 말한다. 단절선: 단절선이란 그 간선을 제거했을 때, 그래프가 두 개 또는 그 이상으로 나누어지는 간선을 말한다. 즉, 제거했을 때 그래프의 connected component의 개수가 증가하는 간선을 말한다. 그럼 어떤게 단절점과 단절선을 빠르게 구할 수 있을까? 그래프 탐색 방법은 DFS를 이용하고, 현재의 정점(노드) 또는 간선을 제거했을 때 현재 정점의 하위에서 현재 정점보다 상위 노드로 접근이 가능하냐를 기준으로 단절점/단절선을 구분하는 방법을 사용한다. (그래프는 tree구.. 더보기 [DFS] BJ_13023, ABCDE [문제의 접근] 어떻게 이 문제에 접근할 수 있을까? 일단, 친구 관계로 주어지는 입력이 graph로 표시될 수 있다는 것을 알아야 한다. 또한 graph의 깊이가 4단계 까지만 진행할 수 있다면 문제의 답으로 도출할 수 있는 것으로 보아 그렇게 깊게 탐색할 필요가 없다는 사실도 알 수 있다. 모든 경우를 다 탐색해 봐야 하는 문제일까? 아니다. 5명이 친구가 되는 케이스가 하나만 있다면 탐색을 종료하고 답을 도출하면 된다. 그렇다면 어떤 알고리즘을 사용해야 할까? 바로 DFS이다. [DFS의 특징] 탐색 가능한 경로의 모든 방향의 Graph를 탐색하여 답을 도출하는 BFS와는 다르게 DFS는 모든 경로를 체크하는 대신 한 경로 우선하여 마지막 깊이까지 진행하여 조건을 만족할 수 있다면 다른 경로를 탐색.. 더보기 이전 1 다음
