백준 9372번: 상근이의 여행 (Python)

접근

처음 문제를 보자마자 답은 n - 1 인 것을 알았다. 그래도 탐색을 통해 답을 구하는 방법이 없을까 고민하여 BFS 알고리즘을 이용하여 풀게 되었다. BFS 알고리즘을 통해 순환하면서 새로운 경로를 통해 새로운 정점을 만나면 카운트해주는 방법이다.

코드

import sys


def bfs(x):
    q = [x]
    visited[x] = 1
    cnt = 0
    while q:
        now = q.pop(0)
        for nx in air[now]:
            if visited[nx] == 0:
                visited[nx] = 1
                cnt += 1
                q.append(nx)
    return cnt


for _ in range(int(sys.stdin.readline())):
    n, m = map(int, sys.stdin.readline().split())
    air = [[] for __ in range(n + 1)]
    visited = [0 for __ in range(n + 1)]
    for i in range(m):
        a, b = map(int, sys.stdin.readline().split())
        air[a].append(b)
        air[b].append(a)
    ans = 0
    for i in range(1, n + 1):
        if visited[i] == 0:
            ans += bfs(i)
    print(ans)

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!