[BOJ/python] 11724: 연결 요소의 개수

문제

✔️ silver 2
그래프 이론
그래프 탐색
너비 우선 탐색
깊이 우선 탐색

문제 흐름

이전에도 풀었던 문제다.
방향이 없는 그래프를 입력받고 그래프의 연결 요소의 개수를 구하는 문제다.
그래프에서 연결 요소란 한 그래프 안에 경로가 존재하는 노드의 집합 하나를 말한다.

위와 같은 그래프의 경우 3개의 연결 요소가 존재한다고 할 수 있다.

하나의 연결 요소를 확인하기 위해서 연결된 모든 노드를 탐색할 필요가 있다.
연결 요소 탐색을 위해 dfs를 이용했다.

방문 확인은 딕셔너리 vst를 만들어 처리했다. 리스트를 사용해도 차이는 없다.

1. 모든 노드를 돌며 vst를 확인하여 방문하지 않은 노드라면 dfs를 실시한다.
2. dfs가 끝나면 cnt를 1 증가시켜 카운트한다.

코드

# 연결 요소의 개수
# graph

import sys
input = sys.stdin.readline

def dfs(g: dict, vst: dict, s: int):
    st = [s]
    vst[s] = 1

    while st:
        x = st.pop()
        for n in g[x]:
            if vst[n]:
                continue
            st.append(n)
            vst[n] = 1

if __name__ == "__main__":
    n, m = map(int, input().split())
    g = {node: [] for node in range(1, n+1)}

    for i in range(m):
        u, v = map(int, input().split())
        g[u].append(v)
        g[v].append(u)
    
    vst = {node: 0 for node in range(1, n+1)}
    cnt = 0
    for s, v in vst.items():
        if not v:
            dfs(g, vst, s)
            cnt += 1
    
    print(cnt)

마무리

제출 내역을 보니 많이 틀리고 맞았었던데 ..
어렴풋이 나는 기억으로는 자꾸 시간초과가 떠서 고민했었는데
결국 문제는 input = sys.stdin.readline을 안해줘서 입력에서 시간이 초과났던 것 같다.
그래서 저 한 줄만 끼워넣은 채 내가 제출했던 코드중 어디까지가 틀린거였는지 계속 다시 제출했던 ... 머쓱...