5248. [파이썬 S/W 문제해결 구현] 6일차 - 그룹 나누기

이번엔 전체 몇 개의 조가 만들어지는지를 알아보는 문제였다. 딱 문제를 봤을 때 "아 이건 그래프랑 DFS를 쓰는 문제야!!"까지는 반사적으로 생각할 수 있었지만, 그래프를 어떻게 구현해야 하는지... 그 부분에서 막혀버렸다. 무방향 그래프니까 graph[a].append(b)와 graph[b].append(a)를 둘 다 해줘야 하는 건 알겠는데, 더 진행할 수 없어서 인터넷의 도움을 받아서 진행했다..

T = int(input())
for test_case in range(1, T+1):
    N, M = map(int, input().split())
    arr = list(map(int, input().split()))
    
    graph = [[] for _ in range(N+1)]    # [0]은 사용x
    visited = [False for _ in range(N+1)]
    
    for i in range(0, len(arr), 2):
        a = arr[i]
        b = arr[i+1]
        graph[a].append(b)
        graph[b].append(a)
    
    count = 0
    
    def dfs(node):
        visited[node] = True
        for neighbor in graph[node]:
            if not visited[neighbor]:
                dfs(neighbor)
    
    for i in range(1, N+1):
        if not visited[i]:
            dfs(i)
            count += 1
            
    print(f"#{test_case} {count}")

그래프를 구현하는 방법도, 그래프 내부를 DFS로 탐색하는 것도 익숙해지도록 많이 연습해야 할 것 같다. 코드만 보면 엄청 쉽다고 생각은 하는데 막상 구현을 못하니...