[BOJ] 22116 창영이와 퇴근

일단 만들어놓은 반례 리스트입니다.

--------
5
5 9 4 4 4
4 9 4 9 4
4 9 4 9 4
4 9 4 9 4
4 4 4 9 4

답 1
--------
3
3 4 1
9 1 8
9 9 9

답 6
---------
3
3 4 1
9 7 8
8 9 9

답 3
----------
6
2 1 2 2 2 2
2 1 2 1 2 2
2 1 2 1 2 2
2 1 2 1 2 2
2 1 2 1 2 2
2 2 2 1 2 2

답 0
-----------
5
4 5 8 7 2
8 6 2 10 9
3 4 15 6 20
4 9 4 3 2
3 2 3 5 1

답 2
-----------
1
아무 숫자

답 0
-----------
3
9 9 9
9 9 9
9 1 3

답 6
---------
5
1 14 15 16 17
2 13 12 19 18
3 10 11 20 21
4 9 8 23 22
5 6 7 24 25
답 1

 

일단 다익스트라에 대해서 아주 대략적으로만 알고 있고, 직접 구현해 본 적은 처음이라서 다익스트라와 bfs, dfs의 차이점에 대해 이해해보았습니다. 보통 bfs나 dfs 문제를 풀 때는 최단 거리 혹은 정해진 거리 중에 ~~한 값을 찾는 문제들이었다면 이 문제는 n n까지 오는 모든 길 중 길 사이사이 경사의 최댓값이 최소인 값을 얻어야 하는 문제였습니다. 이것을 만약 bfs나 dfs로 풀 방법을 생각해보았습니다.

다음과 같이 n=5인 경우의 이동 거리(숫자는 이동 순서)

최소의 경우 중 하나

1
2
3
4
5	6	7	8	9

......

그 사이의 무수한 경우..

.......

최대의 경우 중 하나

1	14	15	16	17
2	13	12	19	18
3	10	11	20	21
4	9	8	23	22
5	6	7	24	25

이전의 방문장소만 재방문하지 않는다는 조건만으로는 최대의 경우같이 괴랄한 루트까지 하나하나 다 비교해보면 당연히 시간초과가 날 것이므로 bfs나 dfs로는 풀 수 없음을 직감했습니다.

다익스트라 알고리즘을 사용하면 해당 위치까지 올 수 있는 최소의 값을 알아 낼 수 있습니다. 그러므로 매번 큐에서 최솟값을 가진 부분부터 탐색을 시작하고, 얻은 값들을 다시 큐에 넣어줍니다. 이 때 매번 정렬을 하는 것은 매우 비효율적이므로 우선순위 큐를 이용하여 매번 최솟값이 맨 앞에 존재하게 해 줄 수 있습니다.  

다익스트라 알고리즘을 통해서라면 다음과 같은 길을 바로 얻을 수 있습니다. 또한 단 한번도 방문하지 않은 부분들도 존재할 수 있습니다.

1	4	5
2	3	6
	8	7
	9
	10	11	12	13

 

파이썬으로 작성한 코드입니다.

일단 크기를 입력받을 변수n과 n*n의 숫자를 입력받을 배열 load 그리고 방문확인과 이 좌표에서 가질수 있는 최솟값을 저장해줄 value_table을 선언?해주었습니다.

우선순위 큐로 사용할 v에 맨 처음 최대 경사(0),x좌표,y좌표를 미리 넣어주고 어차피 무조건 break 되게 되어있으므로 while true로 그냥 써주었습니다.

매번 x,y까지의 최대 경사가 가장 작은 값을 pop시키고 상하좌우로 이동시켰을 때 n*n 범위 안이고(nx,ny), 그 이동한 좌표를 방문한 적이 없다면 v에 현재 좌표(x,y)와 이동한 좌표(nx,ny)의 경사값과 기존의 경사를 max연산시켜주었습니다. 왜냐하면 우선순위 큐에 사용할, 맨 앞의 값은 현재 이동하고 있는 경로에서 가장 큰 경사값이기 때문에 그보다 큰 값이 등장한다면 그것으로 바꿔주어야 하기 때문에 해주었습니다. 그렇게 반복하다보면 무조건 n,n에 도착하게 되고 그때 pop해준 값이 경로상의 최대 경사의 최솟값이므로, 그것을 출력해주고 break해서 끝내주었습니다.

from sys import stdin
from heapq import *

input=stdin.readline
dx,dy=[0,0,1,-1],[1,-1,0,0]

n=int(input())
load=[list(map(int,input().split())) for i in range(n)]
value_table=[[-1 for i in range(n)]for j in range(n)]

v=[[0,0,0]]

while True:
    lean,x,y=heappop(v)
    if value_table[y][x]!=-1:
        continue
    if y==n-1 and x==n-1:
        print(lean)
        break
    value_table[y][x]=lean
    for i in range(4):
        nx=x+dx[i]
        ny=y+dy[i]
        if 0<=nx<n and 0<=ny<n:
            if value_table[ny][nx]!=-1:
                continue
            heappush(v,[max(abs(load[y][x]-load[ny][nx]),lean),nx,ny])

지금까지 중에 제일 오래걸린 것 같은데, 이게 골드4가 맞나 싶습니다;;

C++로 구현하기에는 아직 실력이 부족해서 포기했습니다..