[백준] 9372번-(Python 파이썬) - Tree

문제링크 : https://www.acmicpc.net/problem/9372

이번 문제는 비행기로 이동 가능한 나라를 양방향 그래프로 저장한 후 bfs로 다음 나라로 이동할 때마다
cnt를 증가시켜서 최종 결과를 출력하면 되는 간단한 문제이다.

import sys
from collections import deque
input = sys.stdin.readline

def bfs(start, g, v):
    q = deque()
    q.append(start)
    v[start] = 1
    cnt = 0
    while q:
        temp = q.popleft()
        for i in g[temp]:
            if v[i] == 0:
                v[i] = 1
                cnt += 1
                q.append(i)
    return cnt
def solution():
    n, m = map(int, input().split())
    graph = [[] for _ in range(n + 1)]
    for _ in range(m):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)
    visit = [0 for _ in range(n + 1)]

    ans = bfs(1, graph, visit)
    print(ans)

t = int(input())
for _ in range(t):
    solution()

이건 풀고 나서 알게된건데...

훨씬 간단한 풀이가 있었다

이번 문제는 애초에 모든 나라가 다 연결되어 있어서 비행기 종류 최소 개수는 그냥 "나라 개수 -1"가 된다... 풀고나서 뒤통수 한대 맞은 기분 ㅠ

import sys
input = sys.stdin.readline
def solve():
  n, m = map(int, input().split())
  for _ in range(m):
    a, b = map(int, input().split())
  print(n-1)
  
for _ in range(int(input())):
  solve()