백준 18352

<특정 거리의 도시 찾기>

그래프 & BFS 문제

난이도 : 실버 2

1. 백준 문제
   백준 18352

2. 코드 알고리즘
   

3. 코드

from collections import deque
myque=deque()
import sys
input=sys.stdin.readline
N, M, K, X = map(int, input().split())
a=[[]for _ in range(N+1)]
checked=[0]*(N+1)

for _ in range(M):
    x,y =map(int, input().split())
    a[x].append(y)

def shortcut(x):
    myque.append(x)
    checked[x]=0
    while myque:
        id=myque.popleft()
        for j in a[id]:
            if not checked[j]:
                checked[j] = checked[id] + 1
                myque.append(j)
shortcut(X)
result=0
for i in range(2, len(checked)):
    if checked[i]==K:
        print(i)
        result+=1
if result == 0 :
    print(-1)

4. 후기

• BFS 문제임!
  중복이 제거되기 위해서는 BFS를 사용하는 것이 용이
  DFS를 사용할경우 모든 경로가 표시됨

• checked 적극 사용하기!
  (visited = checked 리스트 의미 동일)
  새로운 리스트를 선언해 경로의 수를 세릴 필요없이
  checked에 체크하면서 연속된 경로의 수를 지날경우 이전의 checked 값 +=1 하면 됨
  ex. 3번 지날 경우
  checked[j] = checked[j-1] + 1
  와 같은 꼴로