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

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

11724번: 연결 요소의 개수

각 숫자가 어느곳으로 연결되었는지를 리스트에 저장하고 DFS(깊이 우선 탐색)를 돌려준다.

코드를 먼저 보고 설명하는 편이 더 나을거 같다.

 

import sys
sys.setrecursionlimit(10000)
input = sys.stdin.readline
def Sol():
  N, M = map(int,input().split())
  A = [[] for _ in range(N)]
  visited = [False] * N
  count = 0

  ## 현재 노드를 방문했으므로 True로 바꾸고 현재 노드에서 연결된 곳이 탐색되지 않았다면 DFS를 돌린다
  def DFS(v):
    visited[v-1] = True
    for i in A[v-1]:
      if not visited[i-1]:
        DFS(i)
        
  ## 어느곳으로 연결 되었는지 저장.
  for _ in range(M):
    s, e = map(int,input().split())
    A[s-1].append(e)
    A[e-1].append(s)

  ## 탐색되지 않은 곳이 있다면 DFS를 돌려준다.
  for i in range(N):
    if not visited[i]:
      count += 1
      DFS(i+1)
  
  print(count)

if __name__ == "__main__":
  Sol()

 

예제 입력 1번의 경우)

DFS 탐색 순서는 1 -> 2 -> 5   /   3-> 4 -> 6  이와 같이 나오고

*DFS탐색 순서는 디버그 모드를 실행하여 코드 과정을 보면 이해하기 쉽다.

2개의 연결순서가 생긴것을 알 수 있다.

주의해야 할 것은 순서는 1번부터 이지만 인덱스는 0번부터인 것에 조심.

그리고 코드의 맨 위에 sys.setrecursionlimit(10000) 은 재귀 깊이의 한계점인데 백준은 기본 기준이 1000으로 되있어서

기준을 10000까지 충분히 늘려주었다.

 

 

글이나 코드에 대한 조언과 질문 모두 환영합니다.