[백준] 9372번 파이썬 _ 상근이의 여행

https://www.acmicpc.net/problem/9372

9372번: 상근이의 여행

문제유형 : BFS

 

문제풀이 :

• BFS로 인접한 국가들을 방문하며 푸는 문제
• 문제에서 '다른국가를 거쳐가도(심지어 이미 방문한국가라도)된다. 라는 말이 나오는데 bfs로풀때 만약 2의 인접한 국가가 3,4라고 했을때 2->3, 2->4 으로 뻗어나가기때문에 2번이 2번 방문되어도 된다 이런의미로 해석하면 된다.
• 큐에 국가를 넣을때마다 비행기를 한번 탔다는것을 의미하므로 count하고 만약 모든 국가가 방문되었다면 bfs를 종료한다.

 

 

정답코드 :

import sys
input = sys.stdin.readline

t = int(input())

from collections import deque


def bfs(start, plane):
    q = deque()
    q.append(start)
    visited[start] = True

    while q:
        # 국가를 모두 방문하면
        if visited.count(True) == n:
            return plane

        curr = q.popleft()

        for node in graph[curr]:
            if not visited[node]:
                q.append(node)
                plane += 1
                visited[node] = True

for _ in range(t):
    n,m = map(int, input().split())
    # n개의 국가를 모두 방문했는가
    visited = [False] * (n+1)

    graph = [[] for _ in range(n+1)]

    for i in range(m):
        a,b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)

    p = bfs(1,0)
    print(p)