[백준 11724 연결 요소의 개수] 파이썬 BFS 너비 우선 탐색 풀이

연결 요소의 개수 문제

11724번: 연결 요소의 개수

뱡향 없은 양방향 그래프가 주어졌을 때 연결 요소를 구하는 문제입니다.

 

 

문제 풀이

연결 요소를 구하는 것은 즉 몇개의 구역으로 나누어져 있는지 구하는 문제입니다.

그래프를 위와 같이 표현했을때 2개의 영역으로 이루어져 있습니다. DFS, BFS 모두 사용해서 풀수 있는 문제입니다. 너비 우선 탐색 BFS로 문제를 풀어보겠습니다.

 

1. 그래프 연결 정보용 행렬 생성
2. BFS를 통해 방문한 노드인지 확인하면서 너비우선 탐색

 

이번 문제에서는 그래프 연결정보를 2차원 배열에 저장했지만, 인접행렬식이 아닌 열결된 정보만 들어있는 인접리스트 형식으로 저장했습니다. 노드의 수를 N, 간선의 수를 E라고 했을 때 최선, 최악 모드 시간복잡도 O(N+E)로 계산됩니다. 너비 우선 탐색을 진행하면서 각 노드는 한번씩 방문하고 간선의 수만큼 탐색을 합니다.

 

 

파이썬 코드