[백준] 22116(파이썬) - 창영이와 퇴근

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

22116번: 창영이와 퇴근

 

• 이 문제를 보고 처음 든 생각은 '이분 탐색을 사용해야 하고, 그래프를 사용해야겠다'였습니다.
• 이분 탐색을 어떻게 구현해야 할지 생각하다가 일단 mid, 기준값을 문제에서 요구하는 최대 경사의 최솟값으로 정하고 문제를 풀었습니다. 처음에 DFS라고 생각하고 풀다가 오히려 시간이 더 오래걸릴 것 같아서 BFS로 풀었고, BFS개념에 이분탐색을 실행하면서 구하는 기준값, mid를 적용시켜주기만 하면 됩니다. 
  
  *수정 : dfs로 구현을 성공했으나 제출했을 때 1000 * 1000 메모리 초과가 발생합니다. 친구의 설명을 들어보니, 몇 가지 경로를 갈지가 아니라 일단 주어진 기준값을 사용해서 해당 좌표로 갈 수 있는지 없는지만 체크해주면 되는 문제이기 때문에 굳이 dfs를 사용하지 않고 bfs로 푸는 것이 더 적절해 보입니다.
• 자세한 설명은 주석을 참고해주시면 감사하겠습니다.

import sys
input = sys.stdin.readline
from collections import deque

# 경사가 최대한 없어야하고, -> 이 경우 창영이 따릉이가 지날 수 있는 경사의 최댓값
# 이분탐색 + 그래프
n = int(input())
graph = [list(map(int,input().split())) for _ in range(n)]
dx = [1,-1,0,0]
dy = [0,0,1,-1]

# 기본적인 bfs함수 구현
def bfs(slope):
    visited =[[0] *n for _ in range(n)]
    q = deque()
    q.append((0,0))
    visited[0][0] = 1
    while q:
        x,y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # 여기서 현재 좌표의 경사와 다음 비교하고 있는 좌표의 경사 값 차이의 절대값이 slope (기준점) 보다 작거나 같으면 ok. 
            # slope보다 작으면 다 이동 가능하니까.
            if 0<= nx < n and 0<= ny <n and visited[nx][ny] == 0 and abs(graph[nx][ny]-graph[x][y]) <= slope:
                # 만약에 n,n에 도착할 수 있을 경우 return 1을 해준다.
                if nx == n-1 and ny == n-1:
                    return 1
                visited[nx][ny] = 1
                q.append((nx,ny))
                
start = 0
# 10000000000 로 해도되고, graph에서 가장 큰 값과 작은값의 차이만큼 하면 메모리를 좀 덜 쓴다.
end =  max(map(max,graph)) - min(map(min,graph))
answer = 0 
while start<=end:
    mid = (start+end) // 2
    # 만약에 bfs가 1이면 -> 도착했으면
    if bfs(mid) == 1:
        # 일단 answer 에 mid, 즉 slope가 될 값을 넣어두고
        answer = mid
        # 더작을 수 있는지? 한번 확인해보고
        end = mid - 1
        # 만약에 도착못했으면 기준점이 너무 작은거니까 mid값을 키워주기 위해 mid = start+1을 해준다.
    else:
        start = mid + 1

print(answer)