알고리즘/백준 문제풀이

[boj] 백준 18352 특정 거리의 도시 찾기 python 풀이

감자156 2023. 7. 22. 13:00
반응형

문제

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

 

18352번: 특정 거리의 도시 찾기

첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개

www.acmicpc.net

 

문제 풀이

단방향 그래프에서 최단거리 찾기 위해 bfs 돌림. visited를 따로 두고 풀었는데, 다른 분들 풀이 보니까 그냥 각 노드에 대한 distance 배열을 만들어서 최단거리로 차차 갱신하며 푸는 법이 일반적 + 더 효율적인듯

 

코드

import sys
input = sys.stdin.readline
import collections

N, M, K, X = map(int,input().split())
MAP = [[] for _ in range(N)]
for _ in range(M):
    A, B = map(int,input().split())
    MAP[A-1].append(B-1)

q = collections.deque()
q.append((X-1,0))

res = set()
visited = [0 for _ in range(N)]
visited[X-1] = 1
while q:
    cur_idx, cnt = q.popleft()
    if cnt == K:
        res.add(cur_idx+1)
    if cnt == K+1:
        break

    for n_idx in MAP[cur_idx]:
        if visited[n_idx] == 0:
            q.append((n_idx, cnt + 1))
            visited[n_idx] = 1
    
if not res:
    print(-1)
else:
    print(*sorted(res), sep='\n')
반응형