특정 거리의 도시 찾기(백준, 18352)

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

https://www.acmicpc.net/source/100095627

 

 

메모리 많이 잡아 먹어서 인접행렬 대신 인접리스트를 사용한 문제

인접행렬과 인접리스트의 차이점

BFS 알고리즘 사용

 

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

city, roads, diste, start = map(int, input().split())

adjM = [[] for _ in range(city + 1)]

for _ in range(roads):
    s, d = map(int, input().split())
    adjM[s].append(d)

dist = [0] * (city + 1)
visited = [False] * (city + 1)

def traverse():
    deq = deque()
    deq.append(start)
    visited[start] = True

    while deq:
        src = deq.popleft()
        for v in adjM[src]:
            if visited[v]:
                continue
            visited[v] = True
            dist[v] = dist[src] + 1
            deq.append(v)

traverse()

found = False
for i in range(1, city + 1):
    if dist[i] == diste:
        print(i)
        found = True

if not found:
    print(-1)