문제 설명
https://www.acmicpc.net/problem/18352
<제한사항>
2 sec
256 MB
<입력>
첫째 줄에 도시의 개수 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을 출력한다.
<예시>
나의 풀이
다익스트라 문제인데, bfs로 풀면 되는데, 나는야 청개구리.
bfs로 풀 수 있는 문제는 dfs로도 풀 수 있는 거 아닌가.
dfs(재귀)를 이용하자 -> 실패(시간초과)
예시는 맞게 나오는데, 재귀를 쓰다보니 다른 테스트 케이스에서 시간초과가 뜨는 것 같다.
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 = [False for _ in range(n)]
cnt = 0
def dfs(a, b):
# print("(", a, ",", b, ")","의 dfs가 호출되었다!!")
if False not in visited:
return -1
global cnt
visited[a-1] = True
cnt += 1
if b in graph[a] and visited[b-1] == False:
return cnt
elif b not in graph[a]:
for item in graph[a]:
return dfs(item, b)
result = []
for i in range(1, n+1):
if i != x:
if dfs(x, i) == k:
result.append(i)
cnt = 0
visited = [False for _ in range(n)]
if len(result) == 0:
print(-1)
else:
for i in result:
print(i)책 풀이
bfs로 풀었다...
from collections import deque
# 도시의 개수, 도로의 개수, 거리 정보, 출발 도시 번호
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)
# 모든 도시에 대한 최단 거리 초기화
distance = [-1] * (n + 1)
distance[x] = 0 # 출발 도시까지의 거리는 0으로 설정
# 너비 우선 탐색(BFS) 수행
q = deque([x])
while q:
now = q.popleft()
# 현재 도시에서 이동할 수 있는 모든 도시를 확인
for next_node in graph[now]:
# 아직 방문하지 않은 도시라면
if distance[next_node] == -1:
# 최단 거리 갱신
distance[next_node] = distance[now] + 1
q.append(next_node)
# 최단 거리가 K인 모든 도시의 번호를 오름차순으로 출력
check = False
for i in range(1, n + 1):
if distance[i] == k:
print(i)
check = True
# 만약 최단 거리가 K인 도시가 없다면, -1 출력
if check == False:
print(-1)다시 나의 풀이
import sys
from collections import deque
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 = [False for _ in range(n + 1)]
result = [-1 for _ in range(n + 1)]
q = deque()
q.append(x)
result[x] = 0
visited[x] = True
while q:
temp = q.popleft()
for item in graph[temp]:
if visited[item] is False:
visited[item] = True
q.append(item)
result[item] = result[temp] + 1
for i in range(1, n + 1):
if result[i] == k:
print(i)
if k not in result:
print(-1)
느낀 점
입력에서 N이 30만, M이 100만이다.
No Excuses