[SWEA/Python] 5250 - 최소비용

 

문제

https://swexpertacademy.com/main/learn/course/lectureProblemViewer.do

 

[문제 요약]

 

출발지에서 도착지까지의 높이가 2차원으로 주어진다.

 

상하좌우로만 이동 할 수 있으며, 이동시 비용은 1, 만약 이동한 곳이 더 높은 지역이라면 높이의 차이 만큼 비용이 증가한다.

 

 

풀이

 

입력으로 받은 값에서 가중치를 2차원 리스트에 저장했고, 가중치를 저장할 2차원 리스트를 큰 값으로 초기화했다.

 

그리고 for 문을 돌려서 N*N의 좌표 중 방문하지 않은 지점 중 가중치가 가장 작은 지점을 탐색하면 시간초과가 났기 때문에, 방문하지 않은 지점이면서 가중치는 초기값이 아닌 좌표를 now_lst에 저장해 탐색했다.

 

그리고 그중에서 가중치의 값이 가장 작은 지점이 선택되면 now_lst에서 제거하고 방문 표시를 한 다음 그 지점을 중심으로 이동할 수 있는 지역들을 now_lst에 저장했다.

 

이 과정을 now_lst가 빌 때 까지 반복해 결과를 출력했다.

 

 

Code

 

 

def Djikstra():
    D_lst=[[1000000]*N for _ in range(N)] # 가중치 2차원 리스트 초기화
    visited=[[False]*N for _ in range(N)] # 방문표시 초기화
    D_lst[0][0]=0 # 초기 출발 지점의 가중치는 0
    now_lst=[(0,0)] 
    while now_lst: 
        min_val=1000000
        a=0 # now_lst에서 제거할 index를 저장(방문했기 때문에 제거)
        for i in range(len(now_lst)):
            y,x=now_lst[i]
            if not visited[y][x] and D_lst[y][x]<min_val: #가중치 비교
                a=i
                min_val=D_lst[y][x]  # 방문하지 않은 지점 중 가장 작은 가중치 저장
                n_y,n_x=y,x
        now_lst.pop(a)
        visited[n_y][n_x]=True # 방문표시
        for i in ((1,0),(0,1),(-1,0),(0,-1)): # 방문한 지점의 주변 탐색
            dy=n_y+i[0]
            dx=n_x+i[1]
            if 0<=dy<N and 0<=dx<N:
                if not visited[dy][dx]:
                    if (dy,dx) not in now_lst: # now_lst에 중복 확인
                        now_lst.append((dy,dx))
                    weight=0
                    if lst[n_y][n_x]<lst[dy][dx]: # 높이가 높은 지역이라면 높이 차이를 저장
                        weight=lst[dy][dx]-lst[n_y][n_x]
                    if D_lst[dy][dx]>D_lst[n_y][n_x]+weight+1: # 가중치 비교 후 작은 값을 저장
                        D_lst[dy][dx]=D_lst[n_y][n_x]+weight+1
    print(f'#{tc} {D_lst[N-1][N-1]}')

for tc in range(1,1+int(input())):
    N=int(input())
    lst=[list(map(int,input().split())) for _ in range(N)]
    visited=[[False]*N for _ in range(N)]
    Djikstra()

 

---

 

처음에 알고리즘을 제대로 짰고, test case도 통과했는데 오답이 떠서 계속 수정했다...

 

알고 보니 초기 출발지점의 가중치를 D_lst[0][0]=0으로 하지 않고, D_lst[0][0]=lst[0][0]으로 기입 했었다...

 

1시간 30분이ㅠㅠ