백준 : 특정 거리의 도시 찾기 - 18352

이 때 1번 도시에서 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 2인 도시는 4번 도시 뿐이다.  2번과 3번 도시의 경우, 최단 거리가 1이기 때문에 출력하지 않는다.

입력

첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개의 자연수 A, B가 공백을 기준으로 구분되어 주어진다. 이는 A번 도시에서 B번 도시로 이동하는 단방향 도로가 존재한다는 의미다. (1 ≤ A, B ≤ N) 단, A와 B는 서로 다른 자연수이다.

출력

X로부터 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 K인 모든 도시의 번호를 한 줄에 하나씩 오름차순으로 출력한다.

이 때 도달할 수 있는 도시 중에서, 최단 거리가 K인 도시가 하나도 존재하지 않으면 -1을 출력한다.

예제 입력 1 

4 4 2 1
1 2
1 3
2 3
2 4

예제 출력 1 

4

예제 입력 2 

4 3 2 1
1 2
1 3
1 4

예제 출력 2 

-1

예제 입력 3 

4 4 1 1
1 2
1 3
2 3
2 4

예제 출력 3 

2
3

 

우선 이 문제는 최단 거리를 찾는 것이 중요하다. DFS는경로의 길이에 상관없이 한 방향으로 최대한 깊숙이 탐색해 들어가는 방식이다. 따라서 시작 노드로부터의 최단 거리를 보장하지 않기 때문에 BFS로 문제를 풀고자 하였다. 

 

여기서 중요한 점은 

1. 어떤 식으로 입력값을 저장할 것인가? (인접 리스트를 사용하고자 했다.)

- 그 이유로는 우선 노드가 단 방향이기도 하고 인접 행렬로 할 경우 메모리 비효율적일 것 같아서 단순 그래프에 append 하는 형식을 생각했다.

 

2. 거리를 어떻게 계산할지? (계산 할 배열을 만들고 각 노드마다 계산되어서 업데이트 하여 그 값을 바탕으로 순회하여 출력하도록)

 

import sys
from collections import deque

# sys.stdin.readline을 짧은 변수명으로 설정
input = sys.stdin.readline

# N, M, K, X를 공백으로 구분해 입력받아 정수형으로 변환
N, M, K, X = map(int, input().split())

# 그래프 정보를 저장할 인접 리스트 초기화 (1번부터 N번 도시까지 사용)
graph = [[] for _ in range(N + 1)]

# distance 배열 초기화 및 BFS 함수 호출
distance = [-1] * (N + 1)
distance[X] = 0 # BFS 함수 밖에서 초기화해도 됨

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


def bfs(graph, start, distance):
    queue = deque([start])

    while queue:
        v = queue.popleft()

        for i in graph[v]:
            if distance[i] == -1:
                distance[i] = distance[v] +1
                queue.append(i)

bfs(graph, X, distance)

found = False

for i in range(1,N+1):
    if distance[i] == K:
        print(i)
        found = True

if not found:
    print(-1)