문제
상근이는 겨울방학을 맞아 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)
주어지는 비행 스케줄은 항상 연결 그래프를 이룬다.출력
테스트 케이스마다 한 줄을 출력한다.
상근이가 모든 국가를 여행하기 위해 타야 하는 비행기 종류의 최소 개수를 출력한다.풀이
import sys
from collections import deque
input = sys.stdin.readline
t = int(input())
# 1. 탐색 시작 노드를 큐에 삽입하고 방문 처리
# 2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리
# 3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복
def bfs(start, cnt):
# queue 에는 방문 예정인 노드를 담고 있다.
queue = deque([start])
visited[start] = True
while queue:
# 현재 방문중인 노드 = 방문 대기중인 큐에서 꺼내기
visiting_node = queue.popleft()
if visited.count(True) == n:
return cnt
# print("graph = ", graph)
# item 에는, 현재 방문중인 노드가 연결된 노드의 번호를 가지고 있다.
for item in graph[visiting_node]:
# print("visiting_node = ", visiting_node)
# print("graph[visiting_node] = ", graph[visiting_node])
# print("item = ", item)
# 그 item이, 방문 처리가 되지 않은 것이라면
if not visited[item]:
# 방문 처리를 해주고
visited[item] = True
# 그 노드를 다음 방문할 큐에 넣는다
queue.append(item)
cnt += 1
for _ in range(t):
n, m = map(int, input().split())
graph = [[] for _ in range(n + 1)]
visited = [False] * (1 + n)
for _ in range(m):
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a)
print(bfs(1, 0))풀이 - 상세
def bfs(start, cnt):
# queue 에는 방문 예정인 노드를 담고 있다.
queue = deque([start])
visited[start] = True
while queue:
# 현재 방문중인 노드 = 방문 대기중인 큐에서 꺼내기
visiting_node = queue.popleft()
if visited.count(True) == n:
return cnt
# print("graph = ", graph)
# item 에는, 현재 방문중인 노드가 연결된 노드의 번호를 가지고 있다.
for item in graph[visiting_node]:
# print("visiting_node = ", visiting_node)
# print("graph[visiting_node] = ", graph[visiting_node])
# print("item = ", item)
# 그 item이, 방문 처리가 되지 않은 것이라면
if not visited[item]:
# 방문 처리를 해주고
visited[item] = True
# 그 노드를 다음 방문할 큐에 넣는다
queue.append(item)
cnt += 1
bfs 메서드를 실행하면, queue 에 시작 노드를 넣는다. --> queue = deque([start])
그리고 시작노드를 방문처리 한다. --> visited[start] = True
그 후 큐가 비어있을 때까지 아래 내용을 반복한다.
visiting_node 에 방문 대기중인 queue 에 있는 노드를 꺼내온다. -> visiting_node = queue.popleft()
graph[visiting_node] 를 통해 그래프에서 방문중인 노드(visiting_node)가 어떤 노드와 연결되어 있는지를 iterator로 받는다.
즉 item 에는, 현재 방문중인 노드(visiting_node)와 연결된 노드들이 들어있다.
만약 현재 방문중인 노드(visiting_node)와 연결된 노드가 여러개라면
--> graph[visiting_node] 가 여러개의 값이면, 그 노드를 한번 씩 다 둘러볼 때 까지 반복을 하는 것이다.
방문기록 리스트에, 방문중인 노드(visiting_node)와 연결된 어떤 노드(item)가, 방문하지 않은 노드라면 --> visited[item],
방문 처리를 해주며 --> visited[item] = True
연결된 노드를 큐에 삽입한다. --> queue.append(item)
만약 이때, 현재 방문중인 노드와 연결된 다른 노드가 아직 남아있다면 연결된 다른 노드를 item 으로 하여 다시 위의 과정을 수행한다.
만약 현재 방문중인 노드와 연결된 다른 노드가 없으면, queue 에서 꺼내온다. -> for-loop 탈출