[백준] 18352번 특정 거리의 도시 찾기 _ Python

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

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

 

 

[초기 접근 방법]

- 특정 노드에서 출발하여, 최단 거리가 K인 모든 도시의 번호를 오름차순으로 출력

- 특정 노드이므로, bfs 탐색과 다익스트라 알고리즘을 사용할 수 있다.

 

 

[생각]

- bfs로는 금방 풀었지만,

   다익스트라 알고리즘 복습하는 문제로 좋았다.

 

 

[코드]

1) bfs

# 풀이 시간 : 20분
# 시간복잡도 : O(N+M)
# 공간복잡도 : O(N+M)
# 참고 : -

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

def bfs():
    q = deque()
    q.append(X)

    # 출발지 노드 최단 거리는 '0'이다.
    # 문제의 조건으로, 출발 도시 X에서 출발 도시 X로 가는 최단 거리는 항상 0이라고 가정
    visited[X] = 0

    while q:
        start = q.popleft()

        # 인접 리스트
        for e in graph[start]:
            # 미방문 노드
            if visited[e] == -1:
                # visited 배열에, 출발지 노드에서 해당 노드까지의 최단거리 기록
                visited[e] = visited[start] + 1
                q.append(e)


# N : 도시의 개수 / M : 도로의 개수 / K : 거리 정보 / X : 출발 도시의 번호
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 = [-1 for _ in range(N+1)]
bfs() # 출발 노드부터, 목적지 노드까지 최단거리를 구하기 위해 bfs

result = []
for i in range(N+1):
    if visited[i] == K:
        result.append(i)

# 최단 거리가 K인 모든 도시의 번호를 한 줄에 하나씩 오름차순으로 출력
if result:
    result.sort()
    for l in result:
        print(l)

# 하나도 존재하지 않으면 -1 출력
else:
    print(-1)

 

 

2) 다익스트라

# 시간복잡도 : O(MlogN) →각 간선마다 우선순위 큐에 삽입 연산이 일어남
#     1) 우선순위 큐에서 꺼낸 현재 노드에 연결된 간선 모두 확인 - 간선의 개수(E) 만큼 확인
#     2) 우선순위 큐에 간선을 넣고 빼는 과정 - logE
#     3) 따라선 모든 간선을 우선순위 큐에 넣고 뺀다고 했을 때 O(ElogE) 의 시간 복잡도를 갖는다.
#     4) 이때, 중복 간선을 포함하지 않는 경우, E는 항상 V^2 이하이다. (모든 노드가 연결 되어 있는 경우 V * (V-1))
#     5) logE < log(V^2)이다. log(V^2)은 2logV이기 때문에 O(logV)로 표현할 수 있다.
#     6) 따라서, 다익스트라 알고리즘 전체 시간 복잡도를 O(ElogV) 로 표현할 수 있다. (ElogE)
# 공간복잡도 : O(N+M)
# 참고 : -

import heapq
import sys
input = sys.stdin.readline

def dijkstra():
    q = []
    heapq.heappush(q, (0, X))
    distance[X] = 0
    
    while q:
        # 출발 거리, 노드 번호
        dist, node = heapq.heappop(q)

        # 이미 갱신된 거리보다 클 시, pass (우선순위에 밀린 원소들)
        if distance[node] < dist:
            continue

        for next_dist, next_node in graph[node]:
            cost = distance[node] + next_dist

            # 시작노드에서 다음노드까지 거리 vs 시작노드에서 현재노드까지 거리 + 인접 거리 
            if distance[next_node] > cost:
                distance[next_node] = cost
                heapq.heappush(q, (cost, next_node)) # cost가 갱신된 노드라면 다시 삽입


# N : 도시의 개수 / M : 도로의 개수 / K : 거리 정보 / X : 출발 도시의 번호
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((1, b)) # 단방향 도로이다.

# 출발지 노드를 중심으로, 각 노드까지의 최단 거리 저장
distance = [float('inf') for _ in range(N + 1)]

dijkstra()

# 결과 출력
result = []
for i in range(1, N+1):
    if K == distance[i]:
        result.append(i)

if result:
    for n in result:
        print(n)
else:
    print(-1)