문제

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	256 MB	53775	17556	11216	30.765%

문제 설명

어떤 나라에는 1번부터 N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다.

이 때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시들의 번호를 출력하는 프로그램을 작성하시오. 또한 출발 도시 X에서 출발 도시 X로 가는 최단 거리는 항상 0이라고 가정한다.

예를 들어 N=4, K=2, X=1일 때 다음과 같이 그래프가 구성되어 있다고 가정하자.

이 때 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

---

내 풀이

문제 아이디어

• 기본적인 문제 풀이 방법은 bfs(너비우선탐색)을 이용하였다.

• 여기에 각 노드별 최단거리를 저장하는 테이블(코드에서는 disance)를 초기화해주고, 인접한 노드를 탐색할때마다의 최단거리를 테이블에 업데이트 해주었다.

  • dp(다이나믹 프로그래밍) 방식 활용

오류 찾기

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

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

def bfs(start):
    q = deque([start])
    visited[start] = 1
    while q:
        node = q.popleft()
        for i in graph[node]:
            if visited[i] == 0: # 방문한 적 없는 노드일 때
                visited[i] = 1 # 방문처리
                q.append(i)
                distance[i] = distance[node]+1
    return True

bfs(x)
if k in distance:
    for i in range(n+1):
        if distance[i] == k:
            print(i)
else:
    print(-1)

• 분명 그래프를 잘 입력하고 bfs도 평소대로 구현했고, 예제도 잘 실행되기에 코드를 제출했다. 근데 출력오류가 발생했다.!!

• 그래서 질문게시판을 찾아본 결과, 내 코드의 오류를 찾았다.

• 바로 해당 문제는 단방향 그래프였던 것 !!!

• 지금까지 양방향 문제를 풀어서 항상 그래프를 구현해줄때, 항상 아래와 같이 데이터를 input해주었는데

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

• 이 문제는 단방향 그래프이므로 아래와 같이 구현해야 한다.

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

---

최종 풀이 코드

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

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

def bfs(start):
    q = deque([start])
    visited[start] = 1
    while q:
        node = q.popleft()
        for i in graph[node]:
            if visited[i] == 0: # 방문한 적 없는 노드일 때
                visited[i] = 1 # 방문처리
                q.append(i)
                distance[i] = distance[node]+1
    return True

bfs(x)
if k in distance:
    for i in range(n+1):
        if distance[i] == k:
            print(i)
else:
    print(-1)

• 입력된 k에 해당하는 distance의 값을 출력해주면 된다.