[BOJ][Python]11724번 풀이

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

11724번: 연결 요소의 개수

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000)

def sol(v):
    if visited[v] == True:
        return
    else:
        visited[v] = True
        for i in range(len(edges)):
            if edges[i][0] == v:
                sol(edges[i][1])
            elif edges[i][1] == v:
                sol(edges[i][0])
        return v
    
n,m = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(m)]
visited = [False for _ in range(n+1)]
cnt = 0
for i in range(1,n+1):
    a = sol(i)
    if i == a:
        cnt += 1
print(cnt)

이번 문제는 약간은 뻔한 dfs입니다. 저는 어지간한 경우가 아니면 2차원 리스트를 이용해서 dfs를 푸는 일이 잘 없긴한데요. 하지만 편하기는 2차원 리스트를 쓰는게 훨씬 편합니다. 흔히들 인접 행렬이다, 인접 리스트다 하시는 말을 들어 보셨을 것 같습니다. 두 방법은 각각 푸는 방법이 차이가 좀 있습니다만 근본이 다른 것은 아니라서 편한대로 푸시면 될 것 같습니다. 저는 그때그때 왔다갔다 합니다. 2차원으로 푸는게 편하겠다 싶으면 그렇게 하고 딱히 아닌 경우엔 메모리를 좀 아껴보려고 1차원으로 푸는 편입니다.

 

접근 방법은 여느 dfs 문제와 다르지 않습니다(bfs도 가능해요). 다만 어떻게 하면 '아 이제 연결된 게 없네 이게 끝인가 보다' 하고 체크를 할 수 있을까요. 저 같은 경우에는 재귀의 특성을 고려해서 재귀 함수가 완전히 종료될 때의 리턴과 처음에 시작했던 노드의 번호가 같으면 카운트를 1 올리는 방식으로 풀었습니다. 이게 무슨 뜻인가 하면 재귀 함수는 함수의 중간에 자기 자신을 호출함으로써 약간 상자 속의 상자를 다시 여는 것과 비슷한 느낌입니다. 예를 들어서 모든 상자의 뚜껑에 번호가 쓰여있다고 해볼게요. 그리고 우리는 맨 처음에 열었던 상자의 번호를 기억할겁니다. 1번 상자 속에 2번, 3번, 4번... 해서 쭉 안에 있는 모든 상자를 열었습니다. 이제 다시 닫으면서 맨 처음에 열었던 상자와 방금 뚜껑을 닫은 상자의 번호를 비교 하는 거에요. n번, n-1번... 모든 상자를 다 닫아야 비로소 처음에 열었던 1번 상자를 닫을 수 있겠죠. 마지막으로 1번 상자를 닫고 방금 닫은 상자와 처음에 열었던 상자의 번호가 1번으로 같으니까 카운트를 하나 세는 겁니다. 물론 이 예시는 지금 문제와는 정확히 들어맞지는 않아요(위 문제는 이미 닫혀있는 1번 상자 속에 있는 2번 상자를 1번을 열지 않고 열어야 하기 때문). 하지만 제가 접근했던 방식이 이런 것이다 라는 부연 설명이라고 이해해주시면 감사하겠습니다.

 

꼭 제가 했던 방법이 아니더라도 dfs를 사용하셨다면 함수가 다 끝날 때 카운트를 세는 방식을 사용하시면 해당 부분을 해결하실 수 있습니다. 도움이 되셨나요? 예전에는 재귀도 제대로 못해서 팀 프로젝트하는 친구에게 시덥잖은 질문을 하던 시절이 있었는데 비록 난이도는 낮을지라도 슬슬 혼자 dfs 문제도 풀게 되니 감회가 새롭네요. 정말 뭐든지 꾸준히 하는게 중요하다는 것을 다시 한 번 느끼는 오늘입니다.