파이썬 코딩테스트 강좌, 최소 비용 구하기

안녕하세요! 이번 글에서는 경로 탐색 문제를 기반으로 한 “최소 비용 구하기” 알고리즘 문제를 다루어 보겠습니다. 코딩 테스트는 IT 기업에서의 취업을 위해 필수적으로 준비해야 할 요소 중 하나입니다. 문제를 해결하기 위한 전략, 알고리즘 이해, 그리고 구현 능력을 기르기 위해 이 글을 통해 단계별로 문제를 풀이해보겠습니다.

문제 설명

최소 비용을 구하는 문제는 주어진 그래프에서 출발점에서 도착점으로 가는 비용의 최솟값을 구하는 문제입니다.
아래와 같은 그래프를 예로 들어봅시다.

    1 --> 2 (비용: 4)
    1 --> 3 (비용: 2)
    2 --> 3 (비용: 1)
    2 --> 4 (비용: 5)
    3 --> 4 (비용: 8)

위 그래프에서 1번 노드에서 4번 노드로 가는 최소 비용을 구하시오.

입력 형식

  • 첫째 줄에 노드의 수 N과 간선의 수 M (1 ≤ N ≤ 1000, 1 ≤ M ≤ 10^4)가 주어진다.
  • 둘째 줄부터 M개의 줄에 각 간선의 정보가 “u v c” 형식으로 주어진다 (u, v는 노드 번호, c는 비용).
  • 마지막 줄에 출발 노드와 도착 노드가 주어진다.

출력 형식

출발 노드에서 목표 노드로 가는 최소 비용을 출력하시오. 경로가 없을 경우 -1을 출력하시오.

문제 접근 방법

이 문제는 그래프의 최단 경로를 구하는 전형적인 문제로, Dijkstra 알고리즘을 사용할 것입니다. Dijkstra 알고리즘은 가중치가 있는 그래프에서 최단 경로를 찾는 데 매우 효율적입니다. 다음과 같은 단계를 통해 알고리즘을 구현할 것입니다.

  1. 입력받기: 노드, 간선 정보를 입력합니다.
  2. 그래프 구조화: 입력받은 간선 정보를 기반으로 그래프를 연결 리스트 형태로 표현합니다.
  3. 우선순위 큐 초기화: 현재 노드에서 인접한 노드의 비용을 관리하기 위해 우선순위 큐를 설정합니다.
  4. Dijkstra 알고리즘 수행: 큐에서 가장 낮은 비용의 노드를 꺼내어 인접한 노드로 가는 비용을 업데이트합니다.
  5. 결과 출력: 목적지에 도달 가능한지 확인하고, 최소 비용을 출력합니다.

코드 구현

import sys
import heapq

def dijkstra(start, goal, graph, n):
    # 비용 테이블 초기화
    INF = float('inf')
    distance = [INF] * (n + 1)
    distance[start] = 0
    queue = []
    heapq.heappush(queue, (0, start))  # (비용, 노드)

    while queue:
        current_cost, current_node = heapq.heappop(queue)

        # 현재 비용이 기존의 최소 비용보다 크면 무시
        if current_cost > distance[current_node]:
            continue

        for neighbor, cost in graph[current_node]:
            new_cost = current_cost + cost

            # 인접 노드의 비용 업데이트
            if new_cost < distance[neighbor]:
                distance[neighbor] = new_cost
                heapq.heappush(queue, (new_cost, neighbor))

    return distance[goal] if distance[goal] != INF else -1

if __name__ == '__main__':
    n, m = map(int, sys.stdin.readline().strip().split())
    graph = [[] for _ in range(n + 1)]

    for _ in range(m):
        u, v, c = map(int, sys.stdin.readline().strip().split())
        graph[u].append((v, c))

    start, goal = map(int, sys.stdin.readline().strip().split())
    result = dijkstra(start, goal, graph, n)
    print(result)

코드 설명

위 코드는 Python에서 Dijkstra 알고리즘을 구현한 것입니다. 입력 파라미터로 시작 노드, 도착 노드, 그래프 구조, 총 노드의 수를 받습니다.

– 비용 테이블 초기화: 노드 수 만큼의 무한대를 가지는 리스트를 초기화합니다. 출발 노드의 비용만 0으로 설정합니다.

– 우선순위 큐 사용: Python의 힙 기능인 heapq를 활용하여 가장 낮은 비용의 노드를 처리합니다.

– 인접 노드 업데이트: 현재 노드와 인접한 노드를 순회하며 최적 비용으로 업데이트합니다.

실행 예시

입력
4 5
1 2 4
1 3 2
2 3 1
2 4 5
3 4 8
1 4

출력
6

이 예시에서는 1번 노드에서 4번 노드로 가는 최소 비용이 6임을 보여줍니다.

그리드 그래프에서의 최소 비용 구하기

위의 문제는 일반적인 그래프이지만, 2D 그리드에서의 최소 비용을 구하는 문제도 있습니다. 아랫부분에서는 2D 배열을 통해 최소 비용을 구하는 방식에 대해 설명하겠습니다.

문제 2: 그리드에서의 최소 비용 구하기

주어진 2D 배열에서 출발점 (0, 0)에서 도착점 (n-1, m-1)까지 이동할 때의 최소 비용을 구해야 합니다. 각 칸의 값은 이동할 때의 비용입니다. 상하좌우로만 이동할 수 있습니다.

입력 형식

3 3
1 2 3
4 1 2
1 5 3

주어진 배열은 다음과 같습니다:

1  2  3
4  1  2
1  5  3

출력 형식

출발점에서 목표점으로 가는 최소 비용을 출력하시오.

문제 접근 방법

이 문제는 다이나믹 프로그래밍을 사용하여 해결할 수 있습니다. 각 칸에서 최소 비용을 계산하여 이전 칸에서 도달할 수 있는 최소 비용을 업데이트하는 방식입니다.

코드 구현

def min_cost_in_grid(grid):
    n = len(grid)
    m = len(grid[0])
    dp = [[0] * m for _ in range(n)]
    dp[0][0] = grid[0][0]
    
    for i in range(n):
        for j in range(m):
            if i == 0 and j == 0:
                continue
            up = dp[i-1][j] if i > 0 else float('inf')
            left = dp[i][j-1] if j > 0 else float('inf')
            dp[i][j] = grid[i][j] + min(up, left)

    return dp[n-1][m-1]

if __name__ == '__main__':
    grid = [
        [1, 2, 3],
        [4, 1, 2],
        [1, 5, 3]
    ]
    result = min_cost_in_grid(grid)
    print(result)

코드 설명

위 코드는 2D 배열의 최소 비용을 구하는 방법을 보여줍니다. dp 배열을 통해 각 칸의 최소 비용을 저장하며, 왼쪽 또는 위쪽에서 오는 비용을 비교하여 현재 칸의 최소 비용을 설정합니다.

실행 예시

출력
8

이 예시에서는 (0, 0)에서 (2, 2)로 가는 최소 비용이 8임을 보여줍니다.

결론

이 글에서는 최소 비용 문제를 해결하기 위한 다양한 접근 방법과 알고리즘을 살펴보았습니다. Dijkstra 알고리즘을 사용한 그래프 문제와 다이나믹 프로그래밍을 활용한 그리드 문제를 통해 코딩 테스트 준비에 도움이 되었기를 바랍니다. 문제 해결 능력을 키우기 위해 다양한 문제에 도전해 보세요!

모든 과정에서 궁금한 점이나 추가적인 질문이 있으시면 댓글로 남겨 주세요. 감사합니다!