[BOJ/백준] 11724번 연결 요소의 개수 (Python 파이썬)

https://www.acmicpc.net/problem/11724

11724번: 연결 요소의 개수

 

시간	제한메모리	제출	정답	맞힌 사람	정답 비율
3 초	512 MB	72076	33043	21673	42.907%

문제

방향 없는 그래프가 주어졌을 때, 연결 요소 (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. N과 M을 입력받고 입력에 따라서 graph를 구성합니다.
   저는 인접 리스트를 활용했는데, 주의할 점은 양방향 모두 정보를 담아야 한다는 점입니다!
   저는 초반에 계속 44%에서 오답처리가 됐었는데 수정 후 정답 처리가 되었습니다.
2. 방문 여부를 확인할 visited 리스트를 선언하였는데, 이때 사용하기 편하도록 N+1 크기로 선언하여 인덱스 자체를 곧 정점 번호로 사용할 수 있도록 하였습니다.
3. DFS는 재귀적으로 간단하게 구현하고,
   visited를 선형적으로 탐색하여 방문한 적이 없다면 DFS를 호출하고 탐색이 끝나면 cnt를 증가시킵니다.

 

import sys
input = sys.stdin.readline
N, M = map(int, input().split())
# 인접 리스트 -> 인덱스를 그대로 정점의 번호로 사용
graph = list([] for _ in range(N+1))

# 연결 요소 개수
cnt = 0

for _ in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

# DFS 실시
visited = [False] * (N+1)
def DFS(x):
    visited[x] = True

    for node in graph[x]:
        if not visited[node]:
            DFS(node)


cnt = 0

for i in range(1, N+1):
    if not visited[i]:
        DFS(i)
        cnt += 1

print(cnt)

 

 

제가 디버깅할 때 패드로 그리면서 할 때도 있지만, 아래의 링크에서 python tutor를 이용할 때도 있습니다.

stack이나 queue를 시각화해주어서 굉장히 편리합니다 :)

https://pythontutor.com/

Python Tutor: Learn Python, JavaScript, C, C++, and Java by visualizing code