99클럽 코테 스터디 30일차 TIL Leetcode Minimum Cost of a Path With Special Roads

문제 & 조건

나의 코드

 

문제를 보는 순간 시작점과 끝점이 고정되고, 최단거리를 구하라는 걸 보자마자 다익스트라 알고리즘을 사용해야겠다는 생각이 들었다.

다만, 어떻게 짜야할지 고민을 하다, 그냥 좌표에 인덱스를 붙여서 평소에 쓰던 다익스트라 알고리즘을 적용 시키는 방법으로 진행하였다.

나의 접근 방법

1. 각 Special road의 좌표들과 시작,끝점을 set으로 중복 없이 구하고, index화 한다.

2. 각 좌표간 cost를 기록해둔 cost_map을 만든다.

3. dijkstra 알고리즘을 사용하여 최단거리를 구한다.

from heapq import *
class Solution:
    def minimumCost(self, start: List[int], target: List[int], specialRoads: List[List[int]]) -> int:
        coord_idx={}
        rev_coord={}
        coords=set()
        coords.add((start[0],start[1]))
        coords.add((target[0],target[1]))
        for x1,y1,x2,y2,cost in specialRoads:
            coords.add((x1,y1))
            coords.add((x2,y2))
        N=len(coords)
        start_idx=-1
        target_idx=-1
        idx=0
        while idx<N:
            for cx,cy in coords:
                coord_idx[idx]=(cx,cy)
                rev_coord[(cx,cy)]=idx
                if [cx,cy]==start:
                    start_idx=idx
                elif [cx,cy]==target:
                    target_idx=idx
                idx+=1
        def diff(a,b):
            return abs(a[0]-b[0])+abs(a[1]-b[1])
        road=[1e9 for _ in range(N)]
        cost_map=[[1e9 for _ in range(N)] for _ in range(N)]
        road[start_idx]=0
        

        for i in range(N):
            for j in range(N):
                cost_map[i][j]=min(diff(coord_idx[i],coord_idx[j]),cost_map[i][j])

        for x1,y1,x2,y2,cost in specialRoads:
            s=rev_coord[(x1,y1)]
            e=rev_coord[(x2,y2)]
            cost_map[s][e]=min(cost_map[s][e],cost)


        queue=[]
        heappush(queue,(0,start_idx))
        coords.discard(coord_idx[start_idx])
        while queue:
            acc,cur_coord=heappop(queue)
            coords.discard(coord_idx[cur_coord])
            if road[cur_coord]<acc:
                continue
            for xi,yi in coords:
                next_coord=rev_coord[(xi,yi)]
                if road[next_coord]>road[cur_coord]+cost_map[cur_coord][next_coord]:
                    road[next_coord]=road[cur_coord]+cost_map[cur_coord][next_coord]
                    heappush(queue,(road[cur_coord]+cost_map[cur_coord][next_coord],next_coord))
        
        return road[target_idx]

 

짧은 회고

사실 좌표별로 튜플화해서 바로 구하면 되는 방법을 쓰는게 더 효율적 방법이라 생각되긴했다.

그에 비해 내 코드는 괜히 좌표를 하나하나 저장하고  비효율적인 코드지만, 일단 이해하기 쉬운 코드로 작성해 본 시도는 잘 한 것 같다.