백준-4485-녹색 옷 입은 애가 젤다지?

정답률이 51%인데 생각보다 어려워서 힘들었다.

결국 혼자 힘으로 다 코드 짜지 못하고 제출했다.

나중에 꼭 다시 풀어보기

문제

녹색 옷 입은 애가 젤다지?

풀이

1. 문제조건 해석

   최단 경로 문제다. 다익스트라 알고리즘을 이용하면 된다.

   다익스트라 알고리즘 이 블로그를 참고했다.

2. 알고리즘

   처음에는 최단 경로 문제인지조차 몰라서 dp이용해서 dfs했다. 당연히 틀렸고. 다익스트라 알고리즘 복습해서 풀었다.

   일반 다익스트라 알고리즘 + 우선순위 큐 자료구조 사용해서 시간을 최소화해야 하는 문제다.

   우선순위 큐 이용하는게 꽤 어려웠다. 꼭 다시 풀어보자.

3. 코드

   참고라고 하지만 거의 이 풀이을 베꼈다.

    from sys import stdin
    import heapq
    def dijkstra(arr, dist, n):
        pq = []
        heapq.heappush(pq, (arr[0][0],0,0))
        while pq:
            v, i, j = heapq.heappop(pq)
            if dist[i][j] < v:
                continue
            if i-1>=0:
                if dist[i-1][j] > v+arr[i-1][j]:
                    dist[i-1][j] = v+arr[i-1][j]
                    heapq.heappush(pq, (dist[i-1][j], i-1, j))
            if i+1<n:
                if dist[i+1][j] > v+arr[i+1][j]:
                    dist[i+1][j] = v+arr[i+1][j]
                    heapq.heappush(pq, (dist[i+1][j], i+1, j))
            if j-1>=0:
                if dist[i][j-1] > v+arr[i][j-1]:
                    dist[i][j-1] = v+arr[i][j-1]
                    heapq.heappush(pq, (dist[i][j-1], i, j-1))
            if j+1<n:
                if dist[i][j+1] > v+arr[i][j+1]:
                    dist[i][j+1] = v+arr[i][j+1]
                    heapq.heappush(pq, (dist[i][j+1], i, j+1))
        return dist[n-1][n-1]
               
   
    input = stdin.readline
    c = 0
    while True:
        c += 1
        n = int(input().rstrip())
        MAXNUM = 9*n*n
        if not n:
            break
        arr = []
        for _ in range(n):
            arr.append([int(x) for x in input().rstrip().split()])
        dist = [[MAXNUM for _ in range(n)] for __ in range(n)]
        print('Problem {}: {}'.format(c, dijkstra(arr, dist, n)))