[TIL] 99클럽 코테 스터디 10일차 TIL - BFS/DFS: 백준 <18352 특정 거리의 도시 찾기 > 문제 풀이 with python

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