[백준] 특정 거리의 도시 찾기 18352번 (python)

문제 : 18352번: 특정 거리의 도시 찾기 (acmicpc.net)

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

풀이 방법

그래프에서 최단 거리를 찾는 문제이다 최단 거리를 찾는 문제는 bfs를 생각해 볼 수 있다.

처음에는 edge의 입력을 이차원 list를 만들어서 연결되어있으면 1 안 되어 있으면 0으로 풀었는데 이러면

메모리 초과로 틀리게 된다 그러므로 2차원 벡터로 i 에서 j로 가는 edge가 있으면 edge[i].append(j) 이런 식으로

메모리를 최소화 해주었다.

queue를 사용해서 bfs를 구현해 주었다 visited를 -1로 초기화해두고(방문 안 한 경우)

방문을 한 경우는 이전 지역의 거리에서 + 1을 해주어 visited에 저장을 해주었다.

from _collections import deque

def sol(start):
    queue = deque()
    queue.append(start)
    visited[start] = 0
    while queue:
        index = queue.popleft()
        for i in edge[index]:
            if visited[i] == -1:
                visited[i] = visited[index] + 1
                queue.append(i)

N, M, K, X = map(int, input().split())
edge = [[] for _ in range(N + 1)]
visited = [-1] * (N + 1)
for i in range(M):
    i, j = map(int, input().split())
    edge[i].append(j)
ans = []
sol(X)
for i in range(1, N+1):
    if visited[i] == K:
        ans.append(i)
if len(ans) == 0:
    print(-1)
else:
    for i in range(len(ans)):
        print(ans[i])