문제
나의 답안(성공 코드)
#최단 거리를 하나씩 확인, k와 일치하면 해당 도시 출력
import sys
from collections import deque #bfs 풀이
input = sys.stdin.readline
n,m,k,x=map(int,input().split())
g=[[] for i in range(n+1)]#n+1개의 노드를 갖는 그래프 생성
for i in range(m):#도로 입력받기
a,b=map(int,input().split())
g[a].append(b)
d=[-1]*(n+1)#노드 간 거리 -1로 초기화
d[x]=0#시작 노드의 거리는 0으로
q=deque([x]) #시작 노드
while q:
start=q.popleft()#현재 노드 pop
for nx in g[start]:#현재 갈 수 있는 모든 노드 탐색
if d[nx]==-1:#방문한적 없는 노드이면
d[nx]=d[start]+1#방문 처리
q.append(nx)
tf=False#k거리에 해당하는 도시가 있는지 없는지 판별
for i in range(1,n+1):
if d[i]==k:
print(i)
tf=True#있음
if tf==False:#없다면 -1
print(-1)
- 첫번째 제출에서 시간 초과가 나서
input = sys.stdin.readline를 사용해주었다.
접근 방법
- 모든 도로의 거리는 1이므로 bfs 문제로 풀어줄 수 있다.
- 출발 도시 x에서 x로 가는 최단 거리는 항상 0이므로 시작 노드를 0으로 초기화해주어야 한다.
- 시작 도시부터 각 도시의 최단 거리를 모두 확인 한 후 k와 일치하는 도시를 차례대로 출력해주면 된다.
다시 풀어보기
