[BOJ/백준 코딩] 상근이의 여행 - PYTHON #9372

소스 코드

import sys

# tc
T = int(input())

for tc in range(T):
    # N 국가 M 비행기 종류
    N,M = map(int,input().split())

    # 비행기 노선도
    board = []

    for q in range(M):
        board.append(sys.stdin.readline().split())

    print(N-1)

---

해결 방법

1. 처음에는 dfs로 문제 접근

-> n,m의 최대 값이 1,000 / 10,000이므로 recursion error 발생할 수 있을 것이라 판단

 

2. bfs로 접근했고, 코드 완성

-> 시간 초과 발생

 

3. 문제를 다시 읽어보니 '가장 적은 종류의 비행기' 이 부분을 제대로 이해하지 못 했었음.

ex) 만약 1 2와 1 3 비행 스케줄을 선택한다면, 1,2,3을 다 돌기 위해서는 1 -> 2 -> 1 -> 3 순서로 지나야 하므로 비행기를 3번 이용해야 한다고 생각했었음.

그러나 이용한 비행 스케줄은 1-2(2-1)와 1-3 2가지임

 

4. 결국 (도시의 수 - 1)가 모든 국가를 여행하기 위해 타야 하는 비행기 종류의 최소 개수가 된다.

-> 그럼에도 시간 초과 발생

 

5. input을 받는 것이 느리기 때문에 시간 초과가 발생한다는 것을 알게 됨

 

6. 여행 스케줄을 input 대신 sys.stdin.readline().split()을 통해서 입력받았고 문제 해결 

 

---

느낀 점

1. 값을 입력받는 여러 방법을 알고있을 필요가 있음을 깨달았음

 

2. input보다 readline으로 입력받는 것이 속도 면에서 더 빠르다

 

3. 문제를 조금 더 신중하게 분석할 필요가 있음

(애초에 N-1이 출력 값이기 때문에 dfs나 bfs로 문제 접근할 필요 없었음)

 

 

ps. 개인적인 코드와 코드를 작성의 이유를 적은 것입니다.

 

오류나 적절치 않은 문법이 존재할 수 있으며, 다른 분들께는 굉장히 비효율적인 방법으로 여겨질 수 있습니다.

 

혹시 개선 사항, 오류 및 문제에 대한 수정 사항 등을 댓글로 남겨주신다면 감사한 마음으로 배우고 수정하겠습니다.