[BOJ] 9372 - 상근이의 여행

문제 링크

9372-상근이의 여행

문제 설명

입력

• 테스트 케이스의 수 T
• T의 줄에 N,M 쌍
  ㄴ 국가의 수 N과 비행기의 종류 M
• M개의 줄에 a,b 쌍
  ㄴ a와 b가 비행기를 타고 이동가능하다.

출력

• 상근이가 모든 국가를 여행하기 위해 타야하는 비행기 종류의 최소 갯수

문제 풀이

트리와 그래프 문제이다.
DFS 와 BFS 를 이용해 풀면되겠다 생각해서 풀어서 맞긴했는데

다른 사람들이 푼거를 보다보니 이 문제의 허점?같은게 있었다.
모든 국가가 연결되어있기때문에 n-1 만 해주면 된다는 것,,?

1. DFS (깊이 우선 탐색) 이용

# 상근이의 여행
import sys
input = sys.stdin.readline

def dfs(start, cnt):
    visited[start] = True

    for s in graph[start]:
        if not visited[s]:
            cnt = dfs(s, cnt+1)
    return cnt

t = int(input())
for _ in range(t):
    n, m = map(int, input().split())

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

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

2. BFS (너비 우선 탐색) 이용

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

def bfs(start, cnt):
    queue = deque([start])
    visited[start] = True

    while queue:
        tmp = queue.popleft()
        cnt += 1

        for g in graph[tmp]:
            if not visited[g]:
                visited[g] = True
                queue.append(g)
    return cnt

t = int(input())
for _ in range(t):
    n, m = map(int, input().split())

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

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

3. 간단한 풀이

# 상근이의 여행
import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    n, m = map(int, input().split())
    for i in range(m):
        a, b = map(int, input().split())

    print(n-1)