[Python] SWExpert - 창용 마을 무리의 개수(D4)

문제출처 - https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWngfZVa9XwDFAQU&categoryId=AWngfZVa9XwDFAQU&categoryType=CODE

SW Expert Academy

def dfs(graph, start):
    visit = []
    stack = [start]

    while stack:
        node = stack.pop()
        if node not in visit:
            visit.append(node)
            stack.extend(graph[node])
    return visit


t = int(input())
for case in range(1, t+1):
    n, m = map(int, input().split())
    graph = {}
    visit = []
    answer = 0

    # 그래프 만들기
    for i in range(m):
        a, b = map(int, input().split())
        graph[a] = graph.get(a, []) + [b]
        graph[b] = graph.get(b, []) + [a]

    for key in graph.keys():
        if key in visit:
            continue
        else:
            visit.extend(dfs(graph, key))
            answer += 1

    answer += n - len(graph)  # 아는 사람이 아예 없는 아싸도 있으니까ㅠㅠ
    print("#%d" % case, answer)

파이썬의 딕셔너리를 이용해 사람들끼리의 관계를 그래프로 만들었다.

 

그래프를 만들고 그래프의 key값만큼 반복문을 돌리면서

 

key값이 이미 방문한 값이면 continue

 

방문한적이 없으면 dfs 함수를 이용해 탐색하게 구현했다.

 

마지막에 관계가 아예 없는 사람도 있으니까 answer에 N - len(graph)한 값을 더해줘야 한다.

 

 

💡딕셔너리의 get함수를 모르겠다면 여기~💡