Today's keyword : BFS
문제설명
https://www.acmicpc.net/problem/18352
이 문제는 주어진 도시와 도로의 정보를 바탕으로, 특정 거리 K에 있는 도시를 찾는 문제입니다.
입력
첫 번째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시 정보 X가 주어집니다.
다음 M개의 줄에는 도로 정보가 주어지며, 각 줄은 두 도시 A와 B를 나타냅니다. 이는 도시 A에서 도시 B로 가는 도로가 있음을 의미합니다.
출력
특정 거리 K에 있는 도시의 번호를 오름차순으로 출력합니다. 만약 그러한 도시가 없다면 -1을 출력합니다.
📌문제풀이
from collections import deque
import sys
input = sys.stdin.readline
N, M, K, X = map(int, input().split()) # N : 도시개수, M : 도로개수, K : 거리정보, X : 출발 도시정보
graph = [[] for _ in range(N + 1)]
# M개의 간선 정보 입력받기
for _ in range(M):
a, b = map(int, input().split())
graph[a].append(b) # a에서 b로의 간선 추가
queue = deque()
queue.append(X)
visited = [-1] * (N + 1) # 거리 정보를 -1로 초기화 (방문하지 않은 도시)
visited[X] = 0 # 출발 도시의 거리는 0
city_lst = []
while queue:
v = queue.popleft()
distance = visited[v]
# 현재 도시에서 K 거리인 도시를 찾기
if distance == K:
city_lst.append(v)
for i in graph[v]:
if visited[i] == -1: # 방문하지 않은 도시인 경우
queue.append(i)
visited[i] = distance + 1 # 이전 거리 + 1
# 결과 출력
city_lst.sort()
if len(city_lst) == 0:
print(-1)
else:
print(*city_lst, sep='\n')
1. 입력 처리:
- 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시 X를 입력받습니다.
- 도시 간의 도로 정보를 그래프 형태로 저장하기 위해 인접 리스트를 초기화합니다.
2. 그래프 구성:
- M개의 도로 정보를 입력받아 인접 리스트 graph에 추가합니다. 각 도시에서 연결된 도시를 리스트로 저장합니다.
3. BFS(너비 우선 탐색) 구현:
- BFS를 사용하여 출발 도시 X에서 시작하여 각 도시까지의 거리를 계산합니다. BFS는 최단 경로를 찾는 데 유리하므로, 특정 거리 K에 있는 도시를 찾는 데 적합합니다.
- BFS를 위해 큐를 사용하고, 출발 도시를 큐에 추가합니다.
4. 거리 정보 업데이트:
- 큐에서 도시를 꺼내면서 해당 도시의 거리 정보를 확인합니다. 현재 도시의 거리가 K인 경우, 해당 도시를 결과 리스트에 추가합니다.
- 인접한 도시를 탐색할 때, 방문하지 않은 도시인 경우에만 큐에 추가하고, 거리 정보를 업데이트합니다.
5. 결과 출력:
- BFS 탐색이 끝난 후, 특정 거리 K에 있는 도시를 오름차순으로 정렬하여 출력합니다. 만약 그러한 도시가 없다면 -1을 출력합니다.
오늘의 회고
초반에 visited 리스트에 0으로 초기화 후, 방문 여부와 방문 거리를 함께 체크했는데 그렇게 되면 거리가 0인 경우와 합쳐지게 된다. 오류 없이 동작하도록 하려면 방문 여부 체크를 -1로 초기화하여 체크하게 바꿔야 한다.
#99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL