[백준/1981/파이썬] 배열에서의 이동

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

1981번: 배열에서 이동

Problem

• n×n짜리의 배열이 하나 있다. 이 배열의 (1, 1)에서 (n, n)까지 이동하려고 한다. 이동할 때는 상, 하, 좌, 우의 네 인접한 칸으로만 이동할 수 있다.
• 이와 같이 이동하다 보면, 배열에서 몇 개의 수를 거쳐서 이동하게 된다. 이동하기 위해 거쳐 간 수들 중 최댓값과 최솟값의 차이가 가장 작아지는 경우를 구하는 프로그램을 작성하시오.

조건

• 첫째 줄에 n(2 ≤ n ≤ 100)이 주어진다. 다음 n개의 줄에는 배열이 주어진다. 배열의 각 수는 0보다 크거나 같고, 200보다 작거나 같은 정수이다.

SOL

문제는 짧고 간단한 문제이지만, 엄청 강렬한 문제이다.

 

완전탐색 

완전탐색으로 모든 경로를 확인 한후 , 최대/최솟값을 비교해보자. 완전탐색은 항상 시간내로 , 이 문제가 해결되는지 확인을 해야한다. 우선, 경로를 모두 볼려면 , DFS로 하는게 적합한데, 경로를 모두 보는 경우는 4^100^2 이므로, 완전탐색을 불가능하다.

 

배열을 이동하기 위해 거쳐간 수들 중 최댓값과 최솟값의 차이를 가장 작게 만드는게, 우리의 목적이다.

제일 직관적이고 생각하기 쉬운 방법은 , 모든 경로를 다 보는것이 겠지만, 위에서 말했듯이 TL이 있으므로 불가능하다.

그렇다면 , 어떻게 생각을 해볼까? 

 

배열의 각 수는 0보다 크거나 같고, 200보다 작거나 같은 정수이다.

우선, 조건에 배열의 숫자에 대해서, 제약사항이 걸려있다.  그리고 생각보다 크지않은 범위이다. 0~200사이의 숫자들의 차이는 아무리 커봤자 200이다.

 

입력으로 주어지는 배열(board)의 값들을 오름차순으로 쫙 나열했다고 생각해보자.

입력으로 주어지는 배열의 값들을 오름차순으로 1차원 배열에 저장

• 이렇게 나열해놓고, 우리가 최솟값, 최댓값의 범위를 딱 정해줄거다. 그리고, 이 범위 내에 있는 값들을 통해서 (n-1,n-1)에 도달 할 수 있는지 확인한다. 
• 만약, 도달 할 수 있다면, min값을 키워서, 더욱 최적화 시킨다.(조건에 맞게 차이가 작아지는 방법은 max값이 작아지던가, min값이 커지던가 2개이다) 만약, 도달 할 수 없다면, max값을 늘려서, 탐색범위를 늘려준다.
• 이 개념이 바로, 투포인터 개념이다.

하지만, 이 문제는 뭔가 범위를 가지고 이렇게 탐색하는 거 보니, 파라메트릭 서치를 해도 괜찮을거 같다.차이의 범위가 0~200이므로, 시작점을 정하면, 차이의 범위를 조절하면서 탐색해나가는 방법을 이용해도 괜찮을듯 하다.

정리하자면, BFS를 탐사하면서, low,high를 조절 해주는 방법으로 구현해주면 된다!

# 배열에서의 이동
import sys
input= sys.stdin.readline
from collections import deque
N=int(input().rstrip())
dx=[0,1,0,-1]
dy=[1,0,-1,0]

board=[]
numLst=set()
for i in range(N):
    tmp=list(map(int,input().split()))
    for value in tmp:
        numLst.add(value)
    board.append(tmp)
# 정렬된 numLST에 투포인터라는 개념을 이용한다.
numLst=sorted(list(numLst))
visited=[[0 for _ in range(N)]for _ in range(N)]
visited_cnt=0

def solve():
    low,high=0,0
    ans=sys.maxsize
    while low<len(numLst) and high<len(numLst):
        # bfs로 탐색햇을 때, 중간지점들이 내가 정한 최소/최대 값 범위에 있는지 확인 
        if bfs(numLst[low],numLst[high]):
            if low==high:
                print(0)
                return
            #무사히 n-1,n-1에 도달했다면, 내가 정한 최소/최대값의 범위를 줄인다. 
            else:
                ans=min(ans,abs(numLst[high]-numLst[low]))
                low +=1
        #만약 도달하지 못했다면, 최댓값을 늘려서, 탐색범위를 늘려본다.
        else:
            high+=1
    print(ans)

def bfs(low,high):
    global visited,visited_cnt
    if board[0][0] < low or board[0][0] > high:
        return False
    visited_cnt+=1
    visited[0][0] =visited_cnt
    dq=deque([(0,0)])
    while dq:
        y,x=dq.popleft()
        if y==N-1 and x==N-1:
            return True
        for k in range(4):
            ny=y+dy[k]
            nx=x+dx[k]
            if not (0<=ny<N and 0<=nx<N):
                continue
            if visited[ny][nx] !=visited_cnt and low<=board[ny][nx]<=high:
                dq.append((ny,nx))
                visited[ny][nx] = visited_cnt
    return False

solve()