18352 특정 거리의 도시 찾기

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

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

 

해결법

-다익스트라(91% 정도에서 틀림)

사실 처음 보고 이 문제는 무조건 다익스트라로 풀어야겠다고 생각했다. 하지만 왜인지 91%에서 계속 틀렸다.

 

-bfs(이게 정답)

1. distance에 모든 노드의 값을 -1로 저장하고 시작 노드만 0으로 바꿔준다.

2. queue를 만들고 시작 노드 번호를 담는다.

3. 연결되어 있는 노드를 다 확인하면서 만약 방문하지 않은 노드(distance의 값이 -1인 노드)이면 현재 노드의 값에서 +1 한 값을 저장한다.

4. 2~3번 과정을 q가 빌 때 까지 반복한다.

5. chk라는 변수를 True로 두고 찾는 값이 생기면 chk를 False로 바꿔준다. 만약 없으면 -1를 출력한다.

 

코드

from collections import deque


n, m, k, x = map(int, input().split())

graph = [[] for i in range(n+1)]

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

distance = [-1] * (n + 1)
distance[x] = 0

q = deque([x])

while q:
    now = q.popleft()

    for i in graph[now]:
        if distance[i] == -1:
            distance[i] = distance[now] + 1
            q.append(i)
 
chk = True

for i in range(1, n+1):
    if distance[i] == k:
        print(i)
        chk = False

if chk:
    print("-1")

 

-다익스트라로 짰다가 틀린 코드

import heapq

n, m, k, x = map(int, input().split())
graph = [[] for i in range(n+1)]

INF = int(1e9)
distance = [INF] * (n+1)

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

def dij(start):
    distance[start] = 0

    q = []
    heapq.heappush(q, (0, start))

    while q:
        cost, now = heapq.heappop(q)

        if cost > distance[now]:
            continue
        
        for i in graph[now]:
            dis = cost + i[1]
            
            if dis < distance[i[0]]:
                distance[i[0]] = dis
                heapq.heappush(q, (dis, i[0]))

dij(x)

answer = []

for i in range(n):
    if distance[i] == k:
        answer.append(i)

if answer:
    for i in answer:
        print(i)
else:
    print(-1)