백준 11724: 연결 요소의 개수 - DFS(파이썬)

연결 요소의 개수  성공

11724번: 연결 요소의 개수

문제

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

입력

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

출력

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

 

내 코드

 

import sys
sys.setrecursionlimit(100000) #Recursion Error 방지

def dfs(n):
    visited[n]=True #dfs 안에 들어오면 일단 그 점 방문 처리.

    for i in range(1, a+1): #모든 점 체크
        if not visited[i] and edge[n][i]: #방문하지 않았고, 존재하는 간선이면
            dfs(i) #dfs 가능


#메인 코드 부분
a,b=map(int, sys.stdin.readline().split())

edge=[] #간선
visited=[] #방문여부

#간선(edge)과 정점별 방문여부(visited) False 초기화.
for _ in range(a+1): #인덱스 접근 편하게 1만큼 더해서 생성(ex:점 개수 6개일 때 edge[6][x]로 접근 가능하게)
    edge.append([False]*(a+1))
    visited.append(False)

#문제에서 주어진 간선 저장
for _ in range(b):
    x,y=map(int, sys.stdin.readline().split())
    edge[x][y]=True #x-y 이어진거나,
    edge[y][x]=True #y-x 이어진거나 같은 간선이므로 이렇게 두번 처리.

cnt=int(0)
for i in range(1, a+1):
    if not visited[i]: #아직 방문하지 않은 점이면 DFS 가능
        dfs(i)
        cnt+=1 #DFS를 빠져나오면 cnt++;

print(cnt)

 

풀이 및 접근)

- 이어진 부분이 한 덩어리가 되어서 그런 덩어리들의 수를 세는 문제이다.

- 한 점에 대해 DFS를 하여 끝까지 이어 나가면서 더 이상 이어 나갈 수 없으면 그것이 한 덩어리의 끝이다.

- 이런 식으로 DFS를 통해 개수를 카운트 하면 된다.

- 메인 코드의 for문에서 dfs()를 몇번 호출 했는지가 곧 덩어리의 개수이다. 메인 코드에서의 dfs()를 빠져 나왔다는 것은 한 덩어리의 끝이어서 빠져나온 것이기 때문이다.

- 정점별 방문여부로 visited[]를 사용했고, 문제에서 주어진 간선을 저장하기 위해 edge[][]를 사용했다. edge를 2차원 리스트로 한 이유는, 1->2 가 이어져 있는거나 2->1 가 이어져 있는 것이 결국 같은 것이기 때문이다. 두 개 모두 표현하여 편하게 사용할 수 있다.