[파이썬] 백준 1981 : 배열에서 이동 (플레5)

[파이썬] 백준 1981 : 배열에서 이동 (플레5)

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

 

---

풀이

방향성 생각

• 첫 풀이는 다차원 BFS + 이분탐색으로 풀이했다.
  • 현재까지 범위 [a,b]를 사용해서 100100201 크기의 배열을 만들고 풀이
  • 최대 최소 범위를 제한시키고 풀이.
  • 하지만, 똑같이 범위차이가 10이어도 [5,15], [10,20]같이 state가 다른 배열(새로운 값 30을 만나는 경우 이전 범위차이가 같더라도 다른 상태에 방문해야한다)을 같은 V에 방문처리 하기때문에 오답
• 두 번째 풀이는 BFS + 이분탐색 완탐처럼 풀이
  • window를 [a,b]로 잡고, 도달할 수 있는지 없는지 풀이
  • limit = b-a라고 했을 때 하나라도 성공하면 그 limit는 성공하고 다음 이분탐색 범위로 풀이

 

---

전체코드

from collections import deque
import sys
input = sys.stdin.readline
inside = lambda x,y : 0<=x<N and 0<=y<N
dire = [(1,0),(0,1),(-1,0),(0,-1)]

N = int(input())
arr = [list(map(int,input().split())) for _ in range(N)]

def bfs(a,b):
    if not (a<=arr[0][0]<=b):
        return False

    Q = deque([(0,0)])
    V = [[False]*N for _ in range(N)]
    V[0][0] = True

    while Q:
        x,y = Q.popleft()
        if (x,y) == (N-1,N-1):
            return True
        for dx,dy in dire:
            nx,ny = x+dx,y+dy
            if inside(nx,ny) and a<=arr[ny][nx]<=b and (not V[ny][nx]):
                V[ny][nx] = True
                Q.append((nx,ny))
    return False

l,r = 0,200
answer = 200
while l <= r:
    limit = (l+r)//2
    possible = False

    for a in range(201-limit):
        if bfs(a,a+limit):
            possible = True
            break

    if possible:
        answer = limit
        r = limit-1
    else:
        l = limit+1

print(answer)

 

---

코멘트

• 상태체크 잘하기...
• python 74% 터져서 pypy로...