[백준] 9372번 상근이의 여행 ★★

💡문제접근

• N개의 국가를 여행하는 비행기가 최소가 되려면 (N-1)개의 비행기가 필요하다.
• 아직 BFS/DFS에 익숙하지 않아 [이것이 코딩 테스트다 with Python] BFS 알고리즘 코드를 보고 공부하면서 코드를 작성했다. 그래프 이론에 대한 부분은 코딩 테스트에 자주 등장하니 공부 열심히 해야겠다.

💡코드(메모리 : 120772KB, 시간 : 396ms, PyPy3로 제출)

from collections import deque

def BFS(graph, start, plane):
    queue = deque([start])
    visited[start] = True

    while queue:
        if visited.count(True) == N:
            return plane
        v = queue.popleft()
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                plane += 1
                visited[i] = True

T = int(input())
for _ in range(T):
    N, M = map(int, input().split())
    graph = [[] for _ in range(N + 1)]
    visited = [False] * (N + 1)
    for _ in range(M):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)
    result = BFS(graph, 1, 0)
    print(result)

💡소요시간 : 40m