BOJ 22116번: 창영이와 퇴근

https://www.acmicpc.net/problem/22116

22116번: 창영이와 퇴근

꽤나 오래 걸린 문제였다..

처음에는 어라 그냥 BFS로 탐색해도 될 것 같은데..? 하고 풀었더니 시간 초과가 나서.. 우선순위큐와 다익스트라를 이용해서 풀어보려고 했는데 머릿속에서 최단경로(?) 를 구하는 문제와 섞여서 로직을 생각하는 게 어려웠다.

또한 다 구현해놓고 왜 답이 안나오지 하다가.. [N-1][N-1] 에 도착하면 반복문을 종료해야 된다는 걸 뒤늦게 깨달았다..

이렇게 구현해도 python으로는 시간초과가 났고 pypy3로 통과할 수 있었는데, 100프로에서 인덱스에러가 난 것은 질문 칸에 고마운 분이.. N=1 일때를 고려해보라고 적어주셔서.. 삽질 많이 안 하고 넘어갔다^^..

 

이분탐색으로 푸는 방법도 있던데 이 방법으로도 한 번 다시 풀어봐야겠다.

import sys, heapq
input = sys.stdin.readline
N = int(input())
arr = []
dist = [[float('INF')]*N for _ in range(N)]
for _ in range(N):
    arr.append(list(map(int, input().split())))

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
h = []
if (N==1):
    print(0)
    sys.exit(0)
heapq.heappush(h, [abs(arr[0][0]-arr[0][1]), 0, 1])
heapq.heappush(h, [abs(arr[0][0]-arr[1][0]), 1, 0])

def solve(X, Y):
    ans = 0
    while(h):
        curcost, now_x, now_y = heapq.heappop(h)
        
        if (dist[now_x][now_y]!=float('INF')):
            continue
        
        dist[now_x][now_y] = curcost
        ans = max(ans, curcost)
        if (now_x == N-1 and now_y == N-1): break #도착하면 종료
        for i in range(4):
            x = now_x + dx[i]
            y = now_y + dy[i]
            if (x>=0 and x<N and y>=0 and y<N):
                if (dist[x][y]==float('INF')):
                    heapq.heappush(h, [abs(arr[now_x][now_y] - arr[x][y]), x,y])

    print(ans)
solve(0,0)