[baekjoon] 백준 9372번(파이썬): 상근이의 여행

문제

9372번: 상근이의 여행

- 상근이는 겨울방학을 맞아 N개국을 여행하면서 자아를 찾기로 마음먹었다.

- 하지만 상근이는 새로운 비행기를 무서워하기 때문에, 최대한 적은 종류의 비행기를 타고 국가들을 이동하려고 한다.

- 이번 방학 동안의 비행 스케줄이 주어졌을 때, 상근이가 가장 적은 종류의 비행기를 타고 모든 국가들을 여행할 수 있도록 도와주자.

- 상근이가 한 국가에서 다른 국가로 이동할 때 다른 국가를 거쳐 가도(심지어 이미 방문한 국가라도) 된다.

- 첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고,

- 각 테스트 케이스마다 다음과 같은 정보가 주어진다.

• 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가 주어진다.
• 이후 M개의 줄에 a와 b 쌍들이 입력된다. a와 b를 왕복하는 비행기가 있다는 것을 의미한다. (1 ≤ a, b ≤ n; a ≠ b) 
• 주어지는 비행 스케줄은 항상 연결 그래프를 이룬다.

알고리즘

- bfs 탐색을 통해 문제를 수행한다.

- 모든 국가가 연결되어 있기 때문에 첫 번째 국가부터 탐색하지 않은 모든 국가를 탐색하여 카운트한다.

코드

문제를 잘 읽어보면 모든 국가가 연결되어 있기 때문에 비행기 종류의 최소개수는 국가의 수에서 1을 빼준 값이 된다.

import sys

# 입력 코드만 적는다.
t = int(sys.stdin.readline())

for i in range(t):
    n, m = map(int, sys.stdin.readline().split())
    
    for j in range(m):
        a, b = map(int, sys.stdin.readline().split())
        
    # 국가의 수 - 1
    print(n - 1)

하지만 문제의 출제 의도를 생각해여 bfs 탐색을 통해 문제를 수행해 보았다.

import sys
from collections import deque # deque를 통해 시간복잡도를 줄였다.


# bfs 함수
def bfs(x):
    # 들려야 할 정점 저장
    queue = deque([x])

    # 현재 노드 방문 처리
    visited[x] = 1
    cnt = 0

    # 큐가 없을때까지 반복
    while queue:

        # 큐에서 하나의 원소를 팝
        queue.popleft()

        # 모든 국가가 연결되어 있으므로 모든 국가 확인
        for i in range(1, n + 1):
            if visited[i] == 0:
                queue.append(i)
                visited[i] = 1
                cnt += 1
    return cnt


# 테스트 케이스만큼 반복
t = int(sys.stdin.readline())
for _ in range(t):
    n, m = map(int, sys.stdin.readline().split())

    # 각 노드가 연결된 정보를 표현
    graph = [[0] * (n + 1) for i in range(n + 1)]
    for i in range(m):
        a, b = map(int, sys.stdin.readline().split())
        graph[b][a] = 1

    # 각 노드의 방문유무
    visited = [0] * (n + 1)

    # 첫 번째 국가부터 탐색
    print(bfs(1))

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법