알면 도움되는 코딩 테스트 유형: 6) #Dijkstra

• 이번에는 코딩 테스트에서 종종 유용하게 사용되는 다익스트라(Dijkstra) 알고리즘에 대해 이야기하려고 합니다. 다익스트라 알고리즘은 최단 경로 문제를 해결하는 데 사용되며, 가중치가 있는 그래프에서 시작 정점으로부터 모든 정점까지의 최단 경로를 찾아줍니다.

 

다익스트라 알고리즘이란?

 

• 다익스트라 알고리즘은 하나의 시작 정점에서 모든 정점까지의 최단 거리를 구하는 그리디한 방법입니다. 이를 위해 우선순위 큐(힙)을 활용하여 현재까지의 최단 거리 정보를 업데이트합니다.
• 다익스트라 알고리즘의 접근 방법은 다음과 같습니다.

 

1. 시작 정점을 선택하고 해당 정점까지의 거리를 0으로 초기화합니다.
2. 나머지 정점들까지의 거리를 무한대로 초기화합니다.
3. 현재 선택된 정점과 연결된 모든 인접한 정점들에 대해 최소 거리 갱신을 시도합니다.
4. 우선순위 큐(힙)을 활용하여 가장 작은 거리 값을 가진 정점을 선택하며 탐색을 진행합니다.
5. 탐색이 완료될 때까지 위 과정을 반복합니다.

 

코딩 테스트에서 다익스트라 알고리즘 문제 접근 방법

 

1. 문제에서 주어진 그래프와 시작 지점, 도착 지점 등의 입력값을 파싱하여 저장합니다.
2. 필요한 경우 그래프 구조나 입력값에 변형이 필요한 경우 처리해줍니다.
3. 다익스트라 알고리즘 함수를 구현하거나 라이브러리 함수를 활용하여 최단 경로 계산 코드를 작성합니다.
4. 계산된 결과값을 출력 형식에 맞게 처리하여 반환하거나 출력합니다.

 

4485번: 녹색 옷 입은 애가 젤다지?

 

  문제  

 

• 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다!
• 젤다의 전설 시리즈의 주인공, 링크는 지금 도둑루피만 가득한 N x N 크기의 동굴의 제일 왼쪽 위에 있다. [0][0]번 칸이기도 하다. 왜 이런 곳에 들어왔냐고 묻는다면 밖에서 사람들이 자꾸 "젤다의 전설에 나오는 녹색 애가 젤다지?"라고 물어봤기 때문이다. 링크가 녹색 옷을 입은 주인공이고 젤다는 그냥 잡혀있는 공주인데, 게임 타이틀에 젤다가 나와있다고 자꾸 사람들이 이렇게 착각하니까 정신병에 걸릴 위기에 놓인 것이다.
• 하여튼 젤다...아니 링크는 이 동굴의 반대편 출구, 제일 오른쪽 아래 칸인 [N-1][N-1]까지 이동해야 한다. 동굴의 각 칸마다 도둑루피가 있는데, 이 칸을 지나면 해당 도둑루피의 크기만큼 소지금을 잃게 된다. 링크는 잃는 금액을 최소로 하여 동굴 건너편까지 이동해야 하며, 한 번에 상하좌우 인접한 곳으로 1칸씩 이동할 수 있다.
• 링크가 잃을 수밖에 없는 최소 금액은 얼마일까?

 
  해결 방법  

 

• 이 문제에서는 다익스트라 알고리즘을 사용하여 최소 비용으로 목적지에 도달하는 방법을 찾습니다.
• 시작 위치에서부터 각 위치까지의 최소 비용을 계산하며 탐색을 진행합니다. 이때도 우선순위 큐를 활용하여 현재까지의 최소 비용에 따라 탐색 순서를 결정합니다.

import sys; input=sys.stdin.readline
import heapq

def dijkstra():
    heap = []
    heapq.heappush(heap, (cave[0][0], 0, 0))
    distance[0][0] = cave[0][0]

    while heap:
        dist, x, y = heapq.heappop(heap)
        if distance[x][y] < dist: continue
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or ny < 0 or nx >= N or ny >= N: continue
            cost = dist + cave[nx][ny]
            if cost < distance[nx][ny]:
                distance[nx][ny] = cost
                heapq.heappush(heap, (cost, nx, ny))

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
cnt = 1

while True:
    N = int(input())
    if N == 0: break
    cave = [list(map(int, input().split())) for _ in range(N)]
    distance = [[float('inf')] * N for _ in range(N)]
    dijkstra()
    print('Problem ' + str(cnt) + ':', distance[N-1][N-1])
    cnt += 1

 

 

2211번: 네트워크 복구

 

  문제  

 

• N(1 ≤ N ≤ 1,000)개의 컴퓨터로 구성된 네트워크가 있다. 이들 중 몇 개의 컴퓨터들은 서로 네트워크 연결이 되어 있어 서로 다른 두 컴퓨터 간 통신이 가능하도록 되어 있다. 통신을 할 때에는 서로 직접 연결되어 있는 회선을 이용할 수도 있으며, 회선과 다른 컴퓨터를 거쳐서 통신을 할 수도 있다.
• 각 컴퓨터들과 회선은 그 성능이 차이가 날 수 있다. 따라서 각각의 직접 연결되어 있는 회선을 이용해서 통신을 하는데 걸리는 시간이 서로 다를 수 있다. 심지어는 직접 연결되어 있는 회선이 오히려 더 느려서, 다른 컴퓨터를 통해서 통신을 하는 것이 더 유리할 수도 있다. 직접 연결되어 있는 회선을 사용할 경우에는 그 회선을 이용해서 통신을 하는 데 드는 시간만큼이 들게 된다. 여러 개의 회선을 거치는 경우에는 각 회선을 이용해서 통신을 하는 데 드는 시간의 합만큼의 시간이 걸리게 된다.
• 어느 날, 해커가 네트워크에 침입하였다. 네트워크의 관리자는 우선 모든 회선과 컴퓨터를 차단한 후, 해커의 공격을 막을 수 있었다. 관리자는 컴퓨터에 보안 시스템을 설치하려 하였는데, 버전 문제로 보안 시스템을 한 대의 슈퍼컴퓨터에만 설치할 수 있었다. 한 컴퓨터가 공격을 받게 되면, 네트워크를 통해 슈퍼컴퓨터에 이 사실이 전달이 되고, 그러면 슈퍼컴퓨터에서는 네트워크를 이용해서 보안 패킷을 전송하는 방식을 사용하기로 하였다. 준비를 마친 뒤, 관리자는 다시 네트워크를 복구하기로 하였다. 이때, 다음의 조건들이 만족되어야 한다.

1. 해커가 다시 공격을 할 우려가 있기 때문에, 최소 개수의 회선만을 복구해야 한다. 물론, 그렇다면 아무 회선도 복구하지 않으면 되겠지만, 이럴 경우 네트워크의 사용에 지장이 생기게 된다. 따라서 네트워크를 복구한 후에 서로 다른 두 컴퓨터 간에 통신이 가능하도록 복구해야 한다.
2. 네트워크를 복구해서 통신이 가능하도록 만드는 것도 중요하지만, 해커에게 공격을 받았을 때 보안 패킷을 전송하는 데 걸리는 시간도 중요한 문제가 된다. 따라서 슈퍼컴퓨터가 다른 컴퓨터들과 통신하는데 걸리는 최소 시간이, 원래의 네트워크에서 통신하는데 걸리는 최소 시간보다 커져서는 안 된다.

• 원래의 네트워크에 대한 정보가 주어졌을 때, 위의 조건을 만족하면서 네트워크를 복구하는 방법을 알아내는 프로그램을 작성하시오.

 
  해결 방법  

 

• 이 문제에서는 네트워크가 고장나서 모든 컴퓨터가 서로 연결되지 않은 상태에서, 각 컴퓨터 사이에 있는 회선을 하나씩만 복구해서 모든 컴퓨터가 서로 연결되게 하려고 합니다.
• 그런데 회선마다 복구하는데 드는 시간이 다르다고 합니다. 이때, 모든 컴퓨터가 서로 연결되게 되는 것은 물론이거니와, 네트워크의 회선을 가장 빨리 복구하는 프로그램을 작성하라는 것입니다.

import sys; input=sys.stdin.readline
import heapq

def dijkstra():
    heap = []
    heapq.heappush(heap, (0, start))
    distance[start] = 0
    
    while heap:
        dist, node = heapq.heappop(heap)
        
        if distance[node] < dist:
            continue
        
        for next_node, weight in graph[node]:
            next_dist = dist + weight
            
            if next_dist < distance[next_node]:
                distance[next_node] = next_dist
                path[next_node] = node
                heapq.heappush(heap, (next_dist, next_node))

N, M = map(int, input().split())
start = 1
graph = [[] for _ in range(N+1)]
distance = [float('inf')] * (N+1)
path = [0] * (N+1)

for _ in range(M):
    u, v, w = map(int, input().split())
    graph[u].append((v, w))
    graph[v].append((u, w))

dijkstra()
print(N-1)
for i in range(2, N+1): print(path[i], i)

• 위 코드에서 dijkstra 함수는 다익스트라 알고리즘을 구현한 것입니다. 주요 변경 사항은 각 정점마다 어디를 거쳐왔는지 저장하는 path 리스트를 추가한 것입니다.
• 각 정점까지의 최단 경로 정보가 저장된 distance 리스트와 함께 path 리스트를 업데이트하며 탐색을 진행합니다. 이렇게 하면 각 정점까지의 최단 경로를 찾을 수 있습니다. 이 문제에서는 기존의 다익스트라 알고리즘에 경로 추적 기능을 추가하여 사용함으로써 보다 복잡한 문제를 해결할 수 있음을 보여줍니다.