[Python] [SWEA] 창용 마을 무리의 개수(7465)

💡 문제 해결

1. 내장 모듈인 defaultdict를 활용하여 마을 정보를 graph형태로 저장
2. 무리 형성의 유무를 파악하기 위한 check리스트 생성
3. check리스트의 값을 기준으로 무리에 대한 정보를 dfs형식으로 탐색하며 갱신
4. 무리 한개의 탐색을 마칠 때마다 정답에 값을 1 추가

🧾 문제 설명

※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다.

창용 마을에는 N명의 사람이 살고 있다.
사람은 편의상 1번부터 N번 사람까지 번호가 붙어져 있다고 가정한다.
두 사람은 서로를 알고 있는 관계일 수 있고, 아닐 수 있다.
두 사람이 서로 아는 관계이거나 몇 사람을 거쳐서 알 수 있는 관계라면,
이러한 사람들을 모두 다 묶어서 하나의 무리라고 한다.
창용 마을에 몇 개의 무리가 존재하는지 계산하는 프로그램을 작성하라.

문제보기

🖨 입출력

📝 풀이

from collections import defaultdict

def dfs(start, stack):
    num = stack.pop()
    check[num] = start
    for link_node in people[num]:
        if check[link_node] == 0:
            stack.append(link_node)
            dfs(start, stack)



for tc in range(1, int(input()) + 1):
    N, M = map(int, input().split())
    arr = list(list(map(int, input().split())) for _ in range(M))
    answer = 0

    people = defaultdict(list)
    check = [0] * (N + 1) 
    for i in range(M):
        people[arr[i][0]].append(arr[i][1])
        people[arr[i][1]].append(arr[i][0])
    
    for i in range(1, N + 1):
        if check[i] == 0:
            dfs(i, [i])
            answer += 1
    
    print(f'#{tc} {answer}')

• 출처: SW Expert Academy
• 링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWngfZVa9XwDFAQU&categoryType=CODE&problemTitle=7465