[#18352] 특정 도시의 거리 찾기

문제

#18352 특정 거리의 도시 찾기
Silver2
적용 알고리즘: 다익스트라 알고리즘

---

풀이 방법

코드 흐름

코드

테스트 케이스는 정답, 시간초과 발생

INF = int(1e9)

def get_smallest_node():
    min_val = INF
    index = 0
    for i in range(1, n + 1):
        if dist[i] < min_val and not visited[i]:
            min_val = dist[i]
            index = i
    return index


def dijkstra(start):
    dist[start] = 0
    visited[start] = True

    for i in path[start]:
        dist[i] = 1

    for i in range(n - 1):
        now = get_smallest_node()
        visited[now] = True
        for j in path[now]:
            cost = dist[now] + 1
            if cost < dist[j]:
                dist[j] = cost


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

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

visited = [False] * (n + 1)
dist = [INF] * (n + 1)


dijkstra(x)
ans = []
for i in range(1, n + 1):
    if dist[i] == k:
        ans.append(i)
if len(ans) > 0:
    for i in range(len(ans)):
        print(ans[i])
else:
    print(-1)

체감 난이도: 4.5/5
헷갈리는 부분이 함수 내부에서 외부의 변수를 건드릴 수 있나? 하긴 당연히 되겠지.. 근데 그러면 인자로 그런애들은 넘겨줄 필요가 없나..? 그러면 또 변수에 global 선언을 해준거는 뭐지..? 갑자기 헷갈려진다.

• 가장 바깥에서 지정한 변수(전역변수)는 함수의 인자로 전달을 해 주지 않아도 내부에서 사용, 변경이 가능하다.
• 무한의 수를 지정할 때에는 INF = int(1e9)