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

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

728x90

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

import sys; input = sys.stdin.readline from collections import deque N, M, K, X = map(int, input().split()) linked_list = [list() for _ in range(N + 1)] for i in range(M): s, e = map(int, input().split()) linked_list[s].append(e) visit = [K + 1 for _ in range(N + 1)] visit[X] = 0 q = deque() q.append(X) while q: cur = q.popleft() for adj in linked_list[cur]: if visit[adj] != K and visit[adj] > visit[cur] + 1: visit[adj] = visit[cur] + 1 q.append(adj) ans = '' for i in range(N + 1): if visit[i] == K: ans += str(i)+'

' print(ans if ans else -1)

연결리스트로 단방향 그래프를 작성하였고 다익스트라를 사용하였다.

visit으로 방문 하지 않은 노드 중에 갱신될만한 곳을 찾아서 큐에 넣었고 끝날때까지 반복한다.

반복문이 끝난 이후 특정 거리의 도시번호를 추가하고 없는 경우엔 -1을 출력하였다.

오랜만에 실버 문제여서 쉽게 풀었다.

from http://sinawi.tistory.com/352 by ccl(A) rewrite - 2021-07-27 21:26:23