99클럽 코테 스터디 10일차 TIL + BFS, 다익스트라

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

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

n, m, k, x = map(int, input().split())
graph = [[] for _ in range(n+1)]
distance = [0] * (n+1)
visited = [False] * (n+1)
answer = []

for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)

def bfs(v):
    que = deque()
    que.append(v)
    visited[v] = True

    while que:
        now = que.popleft()
        for i in graph[now]:
            if not visited[i]: # 방문하지 않음
                visited[i] = True
                distance[i] = distance[now] + 1
                que.append(i)
                if distance[i] == k:
                    answer.append(i)

bfs(x)

if len(answer) == 0:
    print(-1)

else:
    answer.sort()
    for i in answer:
        print(i, end='\n')

• 최단거리를 구하여 answer를 구하므로 bfs 알고리즘을 사용했다.
• distance 배열만으로 값이 0이냐 아니냐를 통해 방문여부를 판단하려고 했지만 계속 틀려 visited 리스트를 추가했다.
• 단방향 도로였기 때문에 graph[a].append(b) 로 graph를 초기화 시켜주었다.
• distance[i]를 구할 때 단순히 +1 이 아닌 이전까지의 거리 (distance[now]) 에 +1을 해주어야 한다.
• 다익스트라 알고리즘으로도 구현이 가능하기 때문에 추후에 다시 풀어볼 것이다....