[python] 백준 9372 상근이의 여행

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

9372번: 상근이의 여행

문제 해결

사실 cnt를 두고 한 번 이동할 때 마다 +1을 해서 정답을 출력했다가 계속 틀렸다.

틀린 이유는 알고 보니 문제를 잘 못 봐서인데 바로 '가장 적은 종류의 비행기를 타고 국가를 이동했을 때 비행기 종류의 수'를 출력 하는 문제이기 때문이다.

답은 무조건 n-1이다. 왜나하면 길이 없어서 왕복할 때는 똑같은 종류의 비행기를 타고 이동하면 되기 때문이다.

 

두 경우 모두 총 두 대의 비행기가 각각 필요하다.

하지만 나는 그래프를 통해서 안가본 곳을 갈 때 새로운 비행기로 갈아탄다는 코드로 풀었다.(사실 이전에 틀리던 코드에서 잘못된 점을 깨달았을 때 고치기 편해서)

 

CODE1

import sys
input = sys.stdin.readline
INF = sys.maxsize
def solve(start, cnt):
    visited[start] = True
    
    for next in graph[start]:
        if visited[next] == False:
            cnt = solve(next, cnt +1)
    return cnt

if __name__=='__main__':
    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)]
        visited[0] = True
        for _ in range(m):
            a, b = map(int, input().split())
            graph[a].append(b)
            graph[b].append(a)
        ans = INF
        ans = solve(1,0)
        print(ans)

CODE2

import sys
input = sys.stdin.readline

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