[백준 1981번] 배열에서 이동(파이썬)

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

1981번: 배열에서 이동

문제는 워낙 심플한데

풀이는 심플하지 않았던 문제.

제가 처음 틀렸던 풀이를 먼저 보겠습니다.

 

#백준 1981 배열에서 이동

#틀린풀이
from heapq import heappop,heappush
from copy import deepcopy
dx=[0,0,1,-1]
dy=[1,-1,0,0]

N=int(input())

room=[]
ma_val=0
mi_val=1e9
for i in range(N):
    tmp=list(map(int,input().split()))
    ma_val=max(ma_val,max(tmp))
    mi_val=min(mi_val,min(tmp))
    room.append(tmp)

q=[]
se=set()
se.add(room[0][0])
heappush(q,[1e9,0,0,se])
answer=1e9
visited=[[False]*N for _ in range(N)]
visited[0][0]=True



while q:

    cnt,x,y,setting=heappop(q)
    if x==N-1 and y==N-1:
        answer=min(answer,cnt)
        continue
    for d in range(4):
        nx=x+dx[d]
        ny=y+dy[d]
        if nx<0 or nx>=N or ny<0 or ny>=N:
            continue
        if visited[nx][ny]==True:
            continue
        tmp_setting=deepcopy(setting)
        go=room[nx][ny]
        tmp_setting.add(go)
        mi=min(tmp_setting)
        ma=max(tmp_setting)
        next=abs(ma-mi)

        visited[nx][ny]=True
        heappush(q,[next,nx,ny,tmp_setting])


print(answer)

이동할때마다 집합에 해당 값을 넣고

최대-최소를 구한다음에 이동하는 케이스입니다.

근데 이렇게 제출하면 바로 틀렸다고 뜹니다.

 

3
2 4 9
1 2 2
9 2 4

 

이것이 반례의 케이스입니다.

위의 코드에 이걸 넣으면

3이 출력이 됩니다.

하지만 정답은 2입니다.

최댓값4에 최소값 2입니다.

방문하면서 최대,최소를 구하다보면

'예상치못한 최대,최소값'이 생깁니다.

 

구글링해보니 이 문제는

이분탐색으로 푸는 문제입니다.

애당초에 최소-최대값을 설정해놓고

배열을 방문하는 방식입니다.

그렇게하면 경로를 탐색할 때의

고정된 바운더리값으로

모든 최소,최댓값을 구할 수 있습니다.

#백준 1981 배열에서 이동
from collections import deque
dx=[0,0,1,-1]
dy=[1,-1,0,0]

N=int(input())

room=[]
ma_val=0
mi_val=1e9
for i in range(N):
    tmp=list(map(int,input().split()))
    ma_val=max(ma_val,max(tmp))
    mi_val=min(mi_val,min(tmp))
    room.append(tmp)

memo={}
def search(diff):
    for i in range(mi_val,ma_val-diff+1):
        start=i
        end=i+diff
        #이미 이 최대최소로 지나간 기록이 있다면
        if (start,end) in memo:
            if memo[(start,end)]==True:
                return True
            else:
                continue
        q=deque()
        #처음시작점이 범위안에 있는지 확인해보기
        #이거 안하면 틀렸다고 뜨더라고요.아무래도 범위를 벗어나는 경우도 있는 것 같습니다.
        if not start<=room[0][0]<=end:
            continue
        q.append([0,0])
        visited=[[False]*N for _ in range(N)]
        visited[0][0]=True

        while q:
            x,y=q.popleft()
            if x==N-1 and y==N-1:
                memo[(start,end)]=True
                return True
            for d in range(4):
                nx=x+dx[d]
                ny=y+dy[d]

                if nx<0 or nx>=N or ny<0 or ny>=N:
                    continue

                if visited[nx][ny]==True:
                    continue
                if start<=room[nx][ny]<=end:
                    visited[nx][ny]=True
                    q.append([nx,ny])
        memo[(start,end)]=False
    return False

def dinary_search(left,right):
    while left<right:
        mid=(left+right)//2
        if search(mid):
            right=mid
        else:
            left=mid+1

    return right

print(dinary_search(0,ma_val-mi_val))

 

이분탐색에 대해서 어렵게만 느껴졌는데

이렇게 문제로 만나면서 배워갔습니다.

이분탐색으로 최대최소를 설정해두고 구하는 방법을

익힐 수 있는 좋은 문제입니다.