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

문제 링크 : https://www.acmicpc.net/problem/1981

1981번: 배열에서 이동

 

접근법을 모르겠어서 알고리즘을 찾아보고 푼 문제이다.

핵심은 투포인터를 이용하는 것이다.

배열의 숫자 리스트를 정렬해서 따로 만들고 투포인터로 최소, 최대값을 결정하고 BFS 실행 후 조정해간다.

 

BFS를 실행할때 시작점과 그리고 중간에 들르는 점들에 대해서 이전에 정한 최소, 최대값 범위에 포함되는지 체크해야한다. 모든 점이 범위를 통과하고 목표점에 도달했다면 투포인터로 최소 최대값을 조정해야한다.

 

BFS를 무사히 통과했다면 두값의 차이를 이용해 답을 갱신하고 둘의 범위를 줄이기 위해 low를 증가시키자.

만약 통과하지 못했다면 범위를 늘리기 위해 high를 증가시키자.

 

이런식으로해서 low나 high가 범위를 벗어날때까지 진행한다.

 

from sys import stdin
from collections import deque

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

n = int(input())

board = []
num_list = set()
for x in range(n):
    board.append(list(map(int, input().split())))
    for num in board[x]:
        num_list.add(num)

num_list = sorted(list(num_list))
visited = [[0]*n for _ in range(n)]
visited_num = 0
def solv():
    low=high=0
    answer = 9876543210

    while low < len(num_list) and high < len(num_list):
        if bfs(num_list[low],num_list[high]):
            if low == high:
                print(0)
                return
            else:
                answer = min(answer, abs(num_list[high]-num_list[low]))
                low += 1
        else:
            high += 1
    print(answer)
def bfs(low,high):
    global visited,visited_num
    if board[0][0] < low or board[0][0] > high:
        return False
    visited_num += 1
    visited[0][0] = visited_num
    q = deque([(0,0)])
    while q:
        x,y = q.pop()

        if x == n-1 and y == n-1:
            return True
        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]

            if point_validator(nx,ny):
                if low <= board[nx][ny] <= high:
                    visited[nx][ny] = visited_num
                    q.appendleft((nx,ny))
    return False
def point_validator(x,y):
    if x < 0 or y < 0 or x >= n or y >= n:
        return False
    elif visited[x][y] == visited_num:
        return False
    return True

solv()