[백준22116] / 창영이와 퇴근 - 다익스트라/최단 경로

 

오랜만에 포스팅~~

 

백준22116

 

 

푼 날짜 : 2024.12.20

푼 문제 : [22116] / 창영이와 퇴근

사용한 언어 : python

알고리즘 : 다익스트라(dijkstra)

 

 

접근방식 :

처음 문제를 풀 때 실수했던 것은 최대라는 말을 빼먹구 코드를 짠 것..

 

창영이가 지날 수 있는 최대 경사의 최솟값을 알아야만 한다.

 

 

"최대 경사" 를 구하는 문제이다.

따라서 경사가 없다고 그냥 0을 출력하면 안된다는 얘기...

 

 

백준 게시판에서 주워온 반례를 첨부한다.

3
20 15 20
5 10 20
2 1 0

 

답은 0이 아니라 5다.

5

 

따라서 최대 경사 max를 구하면서 그 값이 가장 작은 수를 구하는 코드를 짜야한다!

 

 

 

코드 :

import sys
import heapq

input = sys.stdin.readline
INF = float("INF")

N = int(input())
graph = []
for _ in range(N):
    lst = list(map(int, input().split()))
    graph.append(lst)

# 4방향 탐색
dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]

def dijkstra(N, graph):
    heap = [(0, 0, 0)]
    dist = [[INF for _ in range(N)] for _ in range(N)]
    dist[0][0] = 0

    while heap:
        now_cost, now_i, now_j = heapq.heappop(heap)
        if dist[now_i][now_j] < now_cost: continue
        
        for i in range(4):
            ny, nx = now_i+dy[i], now_j+dx[i]

            if 0<=ny<N and 0<=nx<N:
            	# 경로상의 최대 경사의 최솟값을 출력하기 위함
                all_cost = max(now_cost, abs(graph[now_i][now_j] - graph[ny][nx]))
                
                if dist[ny][nx] > all_cost:
                    dist[ny][nx] = all_cost
                    heapq.heappush(heap, (all_cost, ny, nx))

    return dist[N-1][N-1]

ans = dijkstra(N, graph)
print(ans)

 

 

헤헤 요즘 쉬운 문제만 풀다가 오랜만에 다시 머리쓰는 알고리즘 풀기!

뇌가 말랑말랑해지는 건 역시 어려운 문제일 때!!!