Question

• 문제 링크:

18352번: 특정 거리의 도시 찾기

• 문제

Answer

from collections import deque

# 입력 첫 줄
# 도시의 개수, 도로의 개수, 거리 저ㅇ보, 출발 도시 번호
n,m,k,x = map(int, input().split())
graph = [[] for _ in range(n+1)] # 도시 번호는 1부터 시작이라 n+1개 만들고 0번째는 사용 X

# 모든 도로 정보 입력받기
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b) # a번째 도시는 b 도시와 연결되어 있다. # 인접리스트 방식

# 모든 도시에 대한 최단 거리 초기화
distance = [-1] * (n+1)
distance[x] = 0 # 출발 도시까지의 거리는 0

# BFS
q = deque([x]) # deque 생성방식 조심! [x]를 넣은 것이 아니라 deque 리스트에 x가 들어감.
while(q):
    now = q.popleft()
    for next_node in graph[now]:
        if distance[next_node] == -1:
            distance[next_node] = distance[now] + 1
            q.append(next_node)

check = False
for i in range(1, n+1):
    if distance[i] == k:
        print(i)
        check = True

if check == False:
    print(-1)

🔍 Logic

문제에서 모든 거리는 1이라고 하였다. → 모든 간선의 비용 = 1 → 너비 우선 탐색(BFS)

😤 What I learned

<aside> 💡 이 문제풀이를 통해서 무엇을 알았나요?

</aside>

🖍️ TIP

<aside> 🔥 파이썬 문법과 관련해서 무엇을 더 공부했나요?

</aside>

Reference