[BOJ_Python] 9372_상근이의 여행

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

9372번: 상근이의 여행

Idea : 트리를 BFS방식 (BFS 방식이 정확하게 맞는진 모르겠지만,,,)으로 모든 점을 탐색해서 몇번만에 탐색이 완료되는지를 세어봤다.

 

 2차원 빈 리스트를 만들어서 각 인덱스의 빈 리스트에 그 인덱스 번호와 연결된 번호를 리스트에 넣어 graph를 만들었다.빈 큐를 만들어서 특정 점과 연결된 점들을 넣을 공간을 만들었고, 특정 점을 방문 했는지를 체크하기 위해 visited라는 빈 리스트를 만들었다.

 첫 시작을 큐에 넣고 큐에서 첫 원소를 pop하면서 그 원소를 start로 지정했다. start를 방문하지 않았다면 start를 visited에 넣고 start와 연결된 점들(graph[start])을 큐에 넣는다. 다시 큐에서 첫 원소를 pop하는 부분부터 반복을 한다.

 큐에 원소가 없을 때까지 반복을 하고 그때마다 반복 횟수를 count한다. 여기서 count값은 방문한 나라 수이기 때문에 탄 비행기 종류는 count값에서 1을 빼주어야한다.

import sys

t = int(input())

for _ in range(t):
    n, m = map(int, sys.stdin.readline().split())
    graph = [[] for _ in range(n+1)]
    for _ in range(m):
        a, b = map(int, sys.stdin.readline().split())
        graph[a].append(b)
        graph[b].append(a)

    q = []
    visited = []
    q.append(1)
    cnt = 0
    while True:
        if len(q) == 0:
            break
        start = q.pop(0)
        if start not in visited:
            visited.append(start)
            q.extend(graph[start])
            # 내 코드가 맞게 돌아가는지 체크하기 위한 코드
            # print(visited)
            # print(q)
            # print('-------------')
            cnt += 1

    print(cnt - 1)

다른 분들의 코드보다 난잡할 수 있습니다 ㅠㅠ