[SWEA] 7465. 창용 마을 무리의 개수 (bfs, union-find)

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

SW Expert Academy

간단한 union-find를 이용해 푸는 방법과, bfs를 이용해 푸는 방법 두 가지가 있다.

 

1. union-find

부모를 자기 자신으로 초기화한 부모리스트를 먼저 생성한 뒤, p1 p2를 받을 때마다 부모를 찾고, 이들을 합쳐주는 (부모를 갱신) 하는 작업을 진행한다. 모든 input을 받은 뒤, 부모 리스트를 돌며 본인이 부모인 경우만 ans +를 해준다.

def find_p(x):
    if x == p[x]:
        return x
    else: return find_p(p[x])


for tc in range(1, int(input())+1):
    n, m = map(int, input().split())
    p = [i for i in range(n+1)]
    for _ in range(m):
        p1, p2 = map(int, input().split())
        p[find_p(p1)] = find_p(p2)

    ans = 0

    for i in range(1, n+1):
        if i == p[i]:
            ans += 1
    print('#{} {}'.format(tc, ans))

2. bfs

그래프 관계를 인접리스트로 구성하고, team이 되었는지 여부를 판단하는 리스트도 생성한다. input을 모두 받은 뒤, 모든 정점을 확인하며 team이 된 적없으면 bfs를 돌며 같은 같은 team일 경우(연결되어 있을 경우)를 갱신해주고 bfs를 한번 돌때마다 새로운 팀을 배정해준다는 뜻이므로 ans+를 해준다.

from collections import deque

def bfs(start):
    q = deque([start])
    team[start] = True
    while q:
        now = q.popleft()
        for next_node in graph[now]:
            if not team[next_node]:
                q.append(next_node)
                team[next_node] = True


for tc in range(1, int(input())+1):
    ans = 0
    n, m = map(int, input().split())
    team = [False]*(n+1)
    graph = [[] for _ in range(n+1)]
    for _ in range(m):
        n1, n2 = map(int, input().split())
        graph[n1].append(n2)
        graph[n2].append(n1)
    for i in range(1, n+1):
        if not team[i]:
            bfs(i)
            ans += 1

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