백준 11724번 연결 요소의 개수 문제풀이, 파이썬

백준 11724번 : 연결 요소의 개수 문제풀이 [파이썬] 

---

<문제>

11724번 문제의 내용은 아래와 같습니다. 

 

 

연결 요소의 개수

 

문제

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

출력

첫째 줄에 연결 요소의 개수를 출력한다.

예제 입력 1 복사

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

예제 출력 1 복사

2

예제 입력 2 복사

6 8
1 2
2 5
5 1
3 4
4 6
5 4
2 4
2 3

예제 출력 2 복사

1

---

 

 

<작성한 코드>

 

---

 

 

<코드 풀이>

본 문제는 dfs를 사용해서 풀기로했다. 

연결되어 있는 정점끼리 끝까지 타고 들어가고, 방문처리를 해나가면서

연결되어 있지 않은 새로운 정점이 나올때만 카운트 +1해주면 쉽게 풀 수 있을거같아서

dfs로 풀어야겠다는 생각이 가장 먼저 들었다. 

 

 

코드의 가장 첫 두줄을 보면 위의 내용을 발견할 수 있다.....

이 부분때문에 애먹어서 계속 정답을 제출해도 런타임 에러, 시간 초과 등등이 나왔었다ㅠ

파이썬의 재귀 깊이 제한은 매우 얕은편이기 때문에

setrecursionlimit()을 사용해 재귀의 최대 깊이를 설정해줘야한다고 한다.

dfs로 알고리즘 문제를 풀때는 꼭 기억해서 주의하자.

 

 

그 다음부터는 평소 dfs 풀때랑 동일하게 접근했다. 

그래프 그리기 위해서 list 만들고

방문여부를 파악하기 위한 visited 리스트도 만들었다.

초기값은 False로 설정해두었다. 

 

 

dfs 구현과 실행 파트는 위와 같다. 

우선 아래쪽의 반복문을 먼저보면

입력받은 정점의 개수만큼 1부터 시작해서 dfs()를 돌리려고했다.

근데 이때, 방문처리가 되지 않은 정점일때만 dfs를 돌리고 카운트 +1을 했다.

why) 예를들어 정점 1, 2, 3이 서로 연결되어있어서 dfs(1)을 할때

이미 2와 3은 방문처리를 하게된다. 즉 연결되어있지 않은 정점들만 방문처리가 안되어있을텐데

그때가 카운트 +1을 해주어야하는 시점이다. 연결 요소의 개수를 세야하니까,,,

 

dfs를 구현한 부분을 보면

일단 방문처리부터 해주고, graph를 확인해서

그 정점과 연결되어있는 정점들을 하나씩 전부 확인한다.

이때 그 정점들이 아직 방문 처리가 되어있지 않다면 

그 정점을 대상으로 또 dfs를 사용해 연결되어 있는 정점들을 하나씩 확인해준다.

 

참고가 필요하다면 아래 게시글을

2023.01.30 - [백준 알고리즘] - 백준 1260번 파이썬 문제풀이 : DFS와 BFS

백준 1260번 파이썬 문제풀이 : DFS와 BFS