백준 알고리즘 풀이 (Gold) 1753번, 1655번

1. 최단 경로 (1753번)

단방향 간선과 간선에 대한 가중치가 주어졌을 때, 시작점에서 다른 정점으로의 최단 경로를 출력하는 문제입니다.

 

정점에서 다른 정점으로 이동하는 최단 거리를 구하는 문제로 다익스트라 알고리즘을 활용했습니다.

 

첫 번째 시도

기존의 최단 거리를 구하는 문제들처럼 dfs와 정점까지의 가중치의 합을 저장하기 위한 dp배열을 선언하여 문제를 풀어주었습니다.

stack = [[K,0]]
dp[K] = 0
while stack:
    node,weight = stack.pop()
    
    for v,w in edges[node]:
        if weight+w<dp[v]:
            dp[v]=weight+w
            stack.append([v,weight+w])

현재 정점까지의 weight의 합 + 다음 정점으로의 간선의 가중치의 합이 현재 dp에 저장되어 있는 가중치 최소값보다 작을 경우 dp에 저장된 값을 바꿔주고 stack에 다시 그 정점과 정점까지의 최소 가중치를 넣어주었습니다.

위와 같이 반복문을 실행하면 이미 가중치를 한 번 구한 접점에 대해 더 작은 접점이 나올 경우 해당 가중치로 다른 접점들로 최소의 가중치로 갈 수 있다는 것이기 때문에 한 번 더 순회하게 됩니다. 그렇기 때문에 시간에 낭비가 있었고, 시간 초과가 결과로 나타났습니다.

 

두 번째 시도

위의 시도처럼 모든 경우의 수를 순회하기 보다는 낮은 가중치부터 순회를 먼저 할 수 있도록 해주어야지만 시간 낭비를 줄일 수 있다고 생각했습니다.

그래서 python 내부에서 우선순위 큐를 구현해주는 PriorityQueue를 통해 다시 구현을 해보도록 했습니다. (가중치의 합을 기준으로 정렬했습니다.)

queue = PriorityQueue()
queue.put((0,K))
dp[K] = 0
while not queue.empty():
    weight,node = queue.get()
    
    if dp[node]<weight:
        continue
    
    for v,w in edges[node]:
        if weight+w<dp[v]:
            dp[v]=weight+w
            queue.put((weight+w,v))

우선순위 큐를 통해 현재까지의 가중치의 합이 가장 낮은 접점부터 순회를 할 수 있도록 했습니다.

모든 경우의 수를 순회하기는 하지만, 중간의 if문을 통해 현재 저장된 가중치의 합보다 높은 가중치가 들어올 경우 continue 시켜줌으로써 시간 낭비를 줄이게 되었습니다.

 

하지만, 시간 초과?! 가 나오게 되었습니다.

여기서 이유는 간선의 입력이 300,000개가 될 수 있다는 것을 보고 좀 더 입력을 빠르게 해주기 위해 input을 바꿔주었습니다.

import sys
input = sys.stdin.readline

그랬더니 해결이 되었습니다~

 

 

2. 가운데를 말해요 (1655번)

숫자를 계속해서 말할 때 현재까지 말한 숫자의 중간값을 출력하는 문제입니다. 현재까지의 숫자 개수가 짝수일 경우 중간 두 수 중 작은 수를 출력해야 합니다.

 

첫 번째 시도

가운데 3가지 수만 저장함으로써 왔다갔다하면 중간 값을 계속 출력 할 수 있을 것이라고 생각했습니다.

하지만, 만약 4, 7, 10 숫자가 저장되었을 경우 3,8,2 가 차례대로 들어온다면 2, 3, 4, 7, 8, 10으로 중간의 세 숫자를 어떻게 저장할지도 의문이었고 저장되지 않은 숫자가 중간 값으로 올 경우가 무조건 있다고 생각했기 때문에 이러한 방법으로는 풀 수 없다는 생각이 들었습니다.

 

두 번째 시도

중간값과 양 옆에 배치한 수들이 모두 정렬되어 있으면 중간값을 다시 찾기 쉽겠다는 생각이 들었습니다. 그래서 중간값을 저장 할 수 있는 변수와 양 옆을 우선순위 큐로 선언해줌으로써 모든 숫자들이 정렬되어 저장될 수 있도록 해주었습니다.

중간 값과 양 옆에 우선순위 큐를 둠으로써 중간값이 왼쪽의 큐에 들어갈 때도 있고, 중간값이 오른쪽 큐로 이동하고 왼쪽큐에서 새로운 중간값이 반환되면 중간값을 항상 지킬 수 있을 것이라고 생각했습니다.

(말로 설명이 어렵다고 생각이 들어 아래 그림으로 설명드리도록 하겠습니다.)

두 개의 priority queue

위와 같이 중간 값과 양 옆의 숫자들을 저장 할 수 있는 우선순위 큐를 선언해줍니다.

왼쪽 우선순위 큐에서 나오는 숫자 중 중간값이 될 수 있는 숫자는 중간 값보다 낮고 왼쪽 큐 안에 있는 숫자 중 가장 큰 수 이므로 내림차순으로 높은 숫자가 먼저 반환되도록 해줍니다. 

오른쪽 우선순위 큐에서 나오는 숫자 중 중간값이 될 수 있는 숫자는 중간 값보다 높고 오른쪽 큐 안에 있는 숫자 중 가장 작은 수이므로 오름차순으로  낮은 숫자가 먼저 반환되도록 해줍니다.

 

현재까지 불린 숫자의 개수가 짝수이냐 홀수이냐에 따라 중간값의 위치가 달라지기 때문에 해당 조건과 새롭게 입력된 숫자가 들어갈 queue의 위치를 확인하여 로직을 짜주면 됩니다.

for i in range(1,N):
    now = nums[i]
    
    if i%2==1:
        if now<=middle:
            leftQueue.put((-now,now))
            rightQueue.put(middle)
            middle = leftQueue.get()[1]
        else:
            rightQueue.put(now)
    else:
        if now<=middle:
            leftQueue.put((-now,now))
        else:
            rightQueue.put(now)
            leftQueue.put((-middle,middle))
            middle = rightQueue.get()

해당 로직은 충분히 생각해본다면 모두 해결 가능하기 때문에 설명은 생략하도록 하겠습니다.

 

 

 

오늘은 골드 문제 두 가지를 풀어봤는데 의도하지 않았지만 모두 우선순위 큐로 해결이 가능하여 쉽게 해결 할 수 있었습니다. 다음 알고리즘 관련 포스팅도 골드문제로 다시 돌아오도록 하겠습니다.