[SWEA] #7465 창용 마을 무리의 개수

문제 링크

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWngfZVa9XwDFAQU

계획

무향 그래프임을 확인했고 인접 리스트를 이용하는 게 공간 복잡도가 더 낮을 것이라고 생각했다. for문을 통해 모든 노드들을 확인하며 아직 방문하지 않았을 경우 카운트를 +1 한 뒤 인접한 노드들에도 방문 처리하도록 계획했다.

코드

T = int(input())
for tc in range(1, T+1):
    N, M = map(int, input().split())
    adj_list = [[] for _ in range(N + 1)]
    visited = [0] * (N + 1)
    ans = 0

    for i in range(M):
        a, b = map(int, input().split())
        adj_list[a].append(b)
        adj_list[b].append(a)

    for node in range(1, N + 1):
        if not visited[node]:
            visited[node] = 1
            ans += 1
            stack = [node]
            while stack:
                now = stack.pop()
                for nxt in adj_list[now]:
                    if not visited[nxt]:
                        visited[nxt] = 1
                        stack.append(nxt)

    print('#{} {}'.format(tc, ans))

풀이 방법

계획한대로 풀이 완료!