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

문제설명

창영이가 가는 경로에서 경사로가 가장 큰 값을 탐색하고 모든 경로에 대한 탐색을 마쳤으면 그 중 최솟값을 구하자!
즉, 창영이는 (1,1)에 있고 (n,n)까지 가는 모든 경로마다 경사로가 가장 큰 값을 고르고, 그 중 가장 작은 값을 고르라는 것이다(내가 말하고도 이해하기 힘드네..).

알고리즘 1

처음 문제를 봤을때 dfs를 통해서 모든 탐색을 돌고 answer에 min값을 갱신하자는 생각을 했다!!
해당 코드는 다음과 같다

import sys
sys.setrecursionlimit(250000)

n = int(input())
board = []
for _ in range(n):
    board.append(list(map(int,input().split())))
    
def dfs(start, board, n, result):
    global answer
    global visit
    
    if start==(n-1,n-1):
        answer = min(answer,result)
        return
    
    y,x = start
    dy = [0,0,-1,1]
    dx = [-1,1,0,0]
    for i in range(4):
        ny = y + dy[i]
        nx = x + dx[i]
        if 0<=ny<n and 0<=nx<n and visit[ny][nx]==0:
            visit[ny][nx]=1
            dfs((ny,nx),board,n,max(result, abs(board[ny][nx]-board[y][x])))
            visit[ny][nx]=0
            
visit = [[0 for _ in range(n)] for _ in range(n)]
visit[0][0]=1
answer = 1000000001
dfs((0,0),board,n,0)
print(answer)

결과는...
메모리 초과 or recursionlimit error...

생각을 해보니 nxn인데 n은 1000까지 존재하고 모든 경로를 탐색하면 1000*1000까지 될테니 아휴...

다른 방법을 생각해보자

알고리즘 2

약간 야매로 다른 방법을 생각했다.
바로 조건중에 경사로가 1,000,000,000까지 존재할 수 있다는 조건을 보고,
보통 이런 조건은 이분탐색에서 많이 나오는 조건인데??
아, 이분탐색을 통해 미리 경사로를 지정하고 board를 탐색하면서 해당 경사로보다 높은 값이 나오면 (n,n)까지 못간다는 결정문제로 바꾸면 되겠구나!!

코드는 다음과 같이 짰다.

from collections import deque

n = int(input())
board = []
for _ in range(n):
    board.append(list(map(int,input().split())))
    
def bfs(start, board, n, k):
    q = deque()
    q.append(start)
    dy = [0,0,-1,1]
    dx = [-1,1,0,0]
    visit = [[0] * n for _ in range(n)]
    visit[0][0] = 1
    while q:
        y,x = q.popleft()
        if (y,x)==(n-1,n-1):
            return True
        
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if 0<=ny<n and 0<=nx<n and visit[ny][nx]==0 and abs(board[ny][nx]-board[y][x]) <= k:
                visit[ny][nx] = 1
                q.append((ny,nx))
        
    return False

def solution(start,board,n):
    if n==1:
        return 0
    _min = 0
    _max = 1000000000
    answer = _max
    while _min<=_max:
        mid = (_min+_max)//2
        if bfs(start,board,n,mid):
            answer = min(answer, mid)
            _max = mid-1
        else:
            _min = mid+1
    return answer
        

print(solution((0,0),board,n))

solution 함수에서 이분탐색을 진행해서 mid값 구하고 해당 mid값을 통해 board에서 (1,1) ~ (n,n) 까지 갈 수 있는 경로가 존재하는지 탐색하는 코드이다.
결과는...

아무리 생각해도 맞게 짠거같은데 왜틀리지 했는데 n=1일 때 고려를 안해서 틀렸습니다...가 뜬것이였다. 이거 땜에 한시간동안 개고생...