[백준/Python] 상근이의 여행 9372

알고리즘 분류 : 그래프 이론, 트리

시간 복잡도 : .

 

Try_1) Success

• queue를 사용하여 접근해보았다

'''
Condition
    - TL = 1s (약 2000만)
    - ML = 256mb (약 64*10만)
    - 2<=N<=1000, 1<=M<=10000
    - T<=100
    - 무방향 그래프
    - 방문한 노드에 재방문 가능

Question
    - 모든 node를 방문하기 위한 최소 간선의 개수를 출력

Access
    - 시작점에서 갈 수 있는 도착지중, 방문하지 않았던 곳을 골라서 방문한다
    - queue를 사용하여 접근한다
'''

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

#define function
def airplane(start):
    dq= deque()
    dq.append(start)
    cnt = 0
    visited.add(start)
    while len(visited) < n:
        stt = dq.popleft()             #queue에서 stt를 가져옴
        for destination in graph[stt]: #stt와 연결된 방문지중
            if destination in visited: 
                continue
            visited.add(destination)   #방문한적 없다면 방문처리
            dq.append(destination)     #queue에 추가
            cnt +=1
    return cnt

#input&set data
T=int(input())
for _ in range(T):
    n,m = map(int,input().split())
    graph = [[] for _ in range(n+1)]
    visited = set()
    for _ in range(m):
        a,b = map(int,input().split())
        #무방향이므로 양쪽으로 연결
        graph[a].append(b)
        graph[b].append(a)
    print(airplane(1))

Try_2)

• 모든 node가 연결되어 있기 때문에, n개의 node를 방문하기 위해 n-1번의 간선을 이동하면 끝나는 문제였다.
  따라서 모든 입력을 받고 n-1을 출력해주면 끝...!

from sys import stdin
input = stdin.readline
t=int(input())
for _ in range(t):
    n,m=map(int,input().split())
    for _ in range(m):map(int,input().split())
    print(n-1)