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

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

11724번: 연결 요소의 개수

 

---

풀이과정

①문제 바라보기

간단한 graph이론 문제다. DFS문제고, 이해를 위해서 문제에서 제시한 예제 2개를 간선과 노드로 표현해봤다.

위의 그림을 보면 1,2,5가 연결되어있고 3,4,6이 연결되어있음을 확일할 수 있다.  따라서 출력값이 2가 되는 것이며,

두번째 그림을 보면 1~6이 모두 어떻게든 연결되어있기에 출력값이 1이 됨을 확인할 수 있다.

 

②아이디어 펼치기

Graph 이론을 안다면 정말 간단하게 끝나는 문항이다.

위의 코드가 DFS유형 문제에서 계속 활용하는 함수 틀이다.

 

굳이 설명을 하자면, DFS유형에서는 graph 리스트와 visited 리스트가 필요하다. visited리스트는 해당 노드에 방문했는지 방문하지 않았는 지를 저장해놓는 용도로 활용된다. 주로 방문 여부를 1과 2 또는 True와 False로 표기한다.

 그리고 함수 코드에 필요한 요소는 시작하는 점이다. 저 함수 코드에서는 v가 그 역할이다. 방문한 즉시 True로 바꿔주고, 해당 graph[v]에서 방문하지 않은 곳이 있다면 재귀를 활용해서 점점 깊게 뻗어 나가는 것이다.

 

 위의 함수를 1회 실행한다면 1번 예제의 경우 1,2,5까지 파고들어갈 수 있다. 그렇다면 어떻게 다른 뭉떵이를 찾아낼까 고민을 해봤는데 생각보다 간단했다.

 

그냥 For문을 돌려서 visited로 코드를 짜면 된다는 사실이다. 저렇게 짠다면 이제 몇개의 덩어리로 이루어져 있는지 알기가 굉장히 편하다. False가 나오는 순간 그 덩어리는 지금 내가 탐색하던 덩어리와 다른 덩어리가 되니깐 if visited[v]==False인 경우 바로 답이 += 1 이 되는 것이기 때문이다.

 

아차 그리고 추가적으로 두 개의 리스트를 만드는 코드는 아래와 같다.

두 리스트의 공통점은 index가 0일 때는 그냥 무시한다는 점이다. 문제풀이의 편의를 위해서 저렇게 하는게 맞다.

 

 

그리고 이 문항의 경우 recursive error에 유의해야한다. 파이썬은 recursion할 수 있는 깊이가 정해져있는데 이 문항의 경우 그 깊이보다 깊게 들어갈 필요가 있었기에 아래와 같은 코드를 추가로 써줘야한다.

sys.setrecursionlimit(10**6)

 

 

③최종 코드

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
def dfs(graph,v,visited):
    visited[v] = True
    for i in graph[v]:
        if not visited[i]:
            dfs(graph,i,visited)

N, M = map(int,input().split())
graph = [[] for _ in range(N+1)]
visited = [False for _ in range(N+1)]
ans = 0
for _ in range(M):
    A, B = map(int,input().split())
    graph[A].append(B)
    graph[B].append(A)
for i in range(1,N+1):
        if visited[i] == False:
            ans += 1
            dfs(graph,i,visited)
print(ans)