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

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

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

문제 풀이:

BFS를 사용해서 그래프를 탐색하면서 최단 거리를 dist[] 배열에 저장하였고, 탐색이 끝난 후에 dist 배열을 돌면서 값이 K인 경우를 출력하였다. K인 경우가 없을 때는 -1을 출력하였다.

 

import sys
from collections import deque

N, M, K, X = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(N+1)]
for _ in range(M):
    A, B = map(int, sys.stdin.readline().split())
    graph[A].append(B)

q = deque()
q.append(X)
dist = [-1]*(N+1)
dist[X]=0
visit = [False]*(N+1)
visit[X] = True

while(q):
    n = q.popleft()
    for i in graph[n]:
        if (visit[i]==False):
            visit[i] = True
            dist[i] = dist[n]+1
            q.append(i)

flag = False
for i in range(1,N+1):
    if (dist[i]==K):
        print(i)
        flag = True
if (flag==False):
    print(-1)

어려웠던 점:

오랜만에 푸니까 BFS 탐색 방법이 헷갈려서 헤맸다. 복습과 꾸준한 문제풀이는 중요하다..