99클럽 코테 스터디 10일차 - 백준 18352번 특정 거리의 도시 찾기 [Python]

https://www.acmicpc.net/problem/18352

 

 

 

# 학습 키워드
1. BFS(너비우선탐색)

2. 최단경로탐색

3. 그래프 표현

 

 

 

# 문제접근방식

1. 그래프 초기화

입력된 도시와 도로 정보를 기반으로 인접 리스트 형식의 그래프를 구성한다

 

2. BFS 탐색

시작 도시에서부터 BFS를 수행하면서 각 도시의 거리를 distance 리스트에 저장한다

 

3. 조건 확인

BFS 탐색 중 특정 거리 k에 도달하면, 해당 도시를 결과 리스트에 추가하고, 최종적으로 정렬하여 출력한다.

 

4. 예외 처리

k 거리만큼 떨어진 도시가 없을 경우 -1을 출력하도록 예외 처리를 추가한다.

 

 

 

 

# 코드작성

from collections import deque
import sys
f = sys.stdin.readline

n, m, k, x = map(int, f().split())
graph = [[] for _ in range(n+1)]
distance = [0] * (n+1)
visited = [False] * (n+1)

for _ in range(m):
    a, b = map(int, f().split())
    graph[a].append(b)

def bfs(start):
    answer = []
    q = deque([start])
    visited[start] = True
    distance[start] = 0
    while q:
        now = q.popleft()
        for i in graph[now]:
            if not visited[i]:
                visited[i] = True
                q.append(i)
                distance[i] = distance[now] + 1
                if distance[i] == k:
                    answer.append(i)
    if len(answer) == 0:
        print(-1)
    else:
        answer.sort()
        for i in answer:
            print(i, end='\n')

bfs(x)

 

 

 

#회고

이 문제를 풀면서 BFS의 활용을 다시 한번 점검할 수 있었습니다. 특히 최단 거리를 계산할 때 BFS가 가지는 장점이 잘 발휘되는 문제였다고 생각합니다. 단순히 특정 거리의 도시에 도달하는 것이 아닌, 최단 거리 조건에 맞추어 예외 상황을 처리해야 했던 점에서 조건 분기와 예외 처리가 중요했습니다.

특히 이 문제는 k 거리에 해당하는 도시가 없을 때 -1을 출력하는 조건을 놓치지 않도록 주의해야 했습니다. 예외 처리를 통해 조건에 따른 출력을 명확히 함으로써 안정적인 코드를 작성할 수 있었습니다.