알고리즘/Python

[python] 이코테 - 화성 탐사

제주도랏맨 2023. 4. 13. 18:37

출처 : 이것이 취업을 위한 코딩테스트다 with Python, 화성 탐사

 

이것이 취업을 위한 코딩 테스트다 with 파이썬

IT 취준생이라면 누구나 가고 싶어 하는 카카오, 라인, 삼성전자의 2016년부터 2020년까지의 코딩 테스트와 알고리즘 대회의 기출문제를 엄선하여 수록하였다.

hanbit.co.kr

 

더보기

 

먼저, 생각해야 할 부분

 

1. 한 곳에서 다른 곳까지 이동할 때 최소 비용을 구하는 문제이다. (최단 거리 문제)

     단, 이동 시 가중치가 다 다르다 -> 다익스트라로 풀어야한다.

2. 가중치 그래프 설정 방법

     - 하나의 칸에 있는 값을 칸을 나가기 위한 값으로 설정한다

     - 칸에 도착할 경우에도 에너지가 소모되므로, 이 경우 최단 거리 return 시 마지막 칸의 값을 별도로 더해주어야한다.

 


 

풀이 : 우선순위 큐

 

import sys
from heapq import heappop, heappush

INF = float('inf')

def solution(n, mars):
    # 다익스트라 -> 하나의 점에서 다른 점까지의 최소 가리

    # 상하좌우로만 간선이 그어진 그래프
    # 칸에서 나가는 간선은 칸을 지나가기 위한 비용
    # return 시 마지막 칸에 도달 시 칸 비용 + 해줘야함.

    # 노드의 개수
    NC = n ** 2

    # 가중치 그래프
    matrix = [[INF if i != j else 0 for j in range(NC)] for i in range(NC)]

    direction = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    # 그래프 초기화
    for r in range(n):
        for c in range(n):
            cur_idx = r * n + c

            for dr, dc in direction:
                nr, nc = r + dr, c + dc

                if not 0 <= nr < n or not 0 <= nc < n:
                    continue

                target_idx = nr * n + nc

                # current_node -> target_node : mars[r][c]
                matrix[cur_idx][target_idx] = mars[r][c]

    # 다익스트라
    min_distance = [INF for _ in range(NC)]
    min_distance[0] = 0

    heap = []
    heappush(heap, (0, 0))
    visited_node = set()

    while len(heap) > 0:
        # 가장 짧은 거리인 노드를 뺸다.
        dis_until_current_node, node_idx = heappop(heap)

        # 방문하지 않았다면, 방문 체크
        if node_idx in visited_node:
            continue

        visited_node.add(node_idx)

        # 현재 노드의 거리 값 + 인접한 노드의 거리 값을 인접 노드까지 최소 거리로 업데이트
        # 인접 노드를 거리값을 우선 순위로 heap에 넣음
        current_node_dis = min_distance[node_idx]

        for near_node_idx in range(NC):
            near_node_dis = matrix[node_idx][near_node_idx]

            # 인접하지 않다면 패스
            if near_node_dis == INF:
                continue

            # 인접한 노드에 한해 최소 거리 갱신
            min_distance[near_node_idx] = min(min_distance[near_node_idx], current_node_dis + near_node_dis)

            # 갱신된 최소 거리를 우선순위로 인접한 노드를 우선순위 큐에 넣음
            heappush(heap, (min_distance[near_node_idx], near_node_idx))

    return min_distance[NC - 1] + mars[n-1][n-1]

n = int(input())
mars = [list(map(int, sys.stdin.readline().rstrip().split())) for _ in range(n)]

print(solution(n, mars))

 


알게 된 점

 

BFS vs Dijkstra(다익스트라)

 

둘 모두 최단 거리 문제를 푸는 방법이 될 수 있지만,

BFS는 가중치가 없는 그래프인 경우에 최단 거리 문제를 푸는 방법이다.

하지만 다익스트라는 가중치가 다양한 경우에 최단 거리 문제를 푸는 방법이다.

 

Reference

최단거리 문제 알고리즘에 대한 궁금증 정리

이것이 취업을 위한 코딩테스트다 with Python