#38. Algorithm28_python) 상근이의 여행_백준 9372

문제) 상근이의 여행

상근이는 겨울방학을 맞아 N개국을 여행하면서 자아를 찾기로 마음먹었다. 

하지만 상근이는 새로운 비행기를 무서워하기 때문에, 최대한 적은 종류의 비행기를 타고 국가들을 이동하려고 한다.

이번 방학 동안의 비행 스케줄이 주어졌을 때, 상근이가 가장 적은 종류의 비행기를 타고 모든 국가들을 여행할 수 있도록 도와주자.

 

상근이가 한 국가에서 다른 국가로 이동할 때 다른 국가를 거쳐 가도(심지어 이미 방문한 국가라도) 된다.

입력)

첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고,

각 테스트 케이스마다 다음과 같은 정보가 주어진다.

• 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가 주어진다.
• 이후 M개의 줄에 a와 b 쌍들이 입력된다. a와 b를 왕복하는 비행기가 있다는 것을 의미한다. (1 ≤ a, b ≤ n; a ≠ b) 
• 주어지는 비행 스케줄은 항상 연결 그래프를 이룬다.

출력)

테스트 케이스마다 한 줄을 출력한다.

• 상근이가 모든 국가를 여행하기 위해 타야 하는 비행기 종류의 최소 개수를 출력한다.

문제 링크) https://www.acmicpc.net/problem/9372

 

---

 

 

 

---

 

Step1) 문제 이해

t = 2   # 테스트 케이스의 수

# 케이스1
n1 = 3   # 국가의 수
m1 = 3   # 비행기의 종류

# 1 2 : 1국과 2국을 연결하는 비행기가 있다.
# 2 3 : 1국과 2국을 연결하는 비행기가 있다.
# 1 3 : 1국과 3국을 연결하는 비행기가 있다.

# 케이스2
n2 = 5
m2 = 4

# 2 1 : 2국과 1국을 연결하는 비행기가 있다.
# 2 3 : 2국과 3국을 연결하는 비행기가 있다.
# 4 3 : 4국과 3국을 연결하는 비행기가 있다.
# 4 5 : 4국과 5국을 연결하는 비행기가 있다.

"""
<출력>
2   # 케이스1에서 상근이가 타야하는 비행기 종류의 최소 개수
4   # 케이스2에서 상근이가 타야하는 비행기 종류의 최소 개수
"""

- 입출력 이해도 쉽지 않았음;;;

 

Step2) 테스트1 : 로직 형식

for _ in range(int(input())):
    n, m = map(int, input().split())
    for _ in range(m):
        a, b = map(int, input().split())
    print('test')
    
>>>
2
3 3
1 2
2 3
1 3
test
5 4
2 1
2 3
4 3
4 5
test

 

Step3) 정답 제출1 : 실패

- '주어지는 비행 스케줄은 항상 연결 그래프를 이룬다' : 다 연결되어 있으므로, 로직이 어찌되었던 정답은 n-1이다.

  - 사실 '연결 그래프'라는 자료구조를 처음 알았음

- 제출시, '시간 초과'ㅜㅠ

for _ in range(int(input())):
    n, m = map(int, input().split())
    for _ in range(m):
        a, b = map(int, input().split())
    print(n-1)
    
>>>
2
3 3
1 2
2 3
1 3
2
5 4
2 1
2 3
4 3
4 5
4

Step4) 정답 제출2 : 성공

- sys.stdin.readline 활용 : 참조 https://velog.io/@yeseolee/Python-%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EC%9E%85%EB%A0%A5-%EC%A0%95%EB%A6%ACsys.stdin.readline

import sys
input = sys.stdin.readline

for _ in range(int(input())):
    n, m = map(int, input().split())
    for _ in range(m):
        a, b = map(int, input().split())
    print(n-1)
    
>>>
2
3 3
1 2
2 3
1 3
2
5 4
2 1
2 3
4 3
4 5
4

 

add) BFS 알고리즘

- 구글링 해보니, BFS 알고리즘이란 걸 활용하는 것이 정석

- 참조 : https://ca.ramel.be/122

- 추후 공부 예정 : https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html 

 

import sys


def bfs(x):
    q = [x]
    visited[x] = 1
    cnt = 0
    while q:
        now = q.pop(0)
        for nx in air[now]:
            if visited[nx] == 0:
                visited[nx] = 1
                cnt += 1
                q.append(nx)
    return cnt


for _ in range(int(sys.stdin.readline())):
    n, m = map(int, sys.stdin.readline().split())
    air = [[] for __ in range(n + 1)]
    visited = [0 for __ in range(n + 1)]
    for i in range(m):
        a, b = map(int, sys.stdin.readline().split())
        air[a].append(b)
        air[b].append(a)
    ans = 0
    for i in range(1, n + 1):
        if visited[i] == 0:
            ans += bfs(i)
    print(ans)

---

# 배운 점

• 연결 그래프
• input = sys.stdin.readline
  • 반복문에서 입력 받을 때, 자원 낭비 방지 및 실행 속도 높이기 위해 사용

 

# 소회

• 문제에서 '연결 그래프'라는 의미를 몰라서 헤맴
  • 예시 입력값을 봤을 때, '어? 다 연결되어 있네? 그럼 예시에서는 n-1 일텐데'라고 생각했으나,
  • 직항이 없는 경우도 있다고 생각했기에 고민을 함
    결론적으로 '연결 그래프'라는 자료 구조(?) 개념이 있음
• 다양한 자료구조를 이해하고, 활용할 수 있는 것이 '근본'이구나...
• '시간 초과' 등장!
  • 앞으로 필요할 때, 'input = sys.stdin.readline'를 이용