[백준 14948] 군대탈출하기(파이썬)

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

14948번: 군대탈출하기

삽질을 참 많이 한 문제.

이 문제는 '도움닫기'입니다.
bfs를 해주면서
'벽타고 넘기기'를 해주면 됩니다.
벽을 탈때에는
이동하는 방향 그대로 한번 더 이동해주면 됩니다.

#백준 14948번 군대탈출하기
from heapq import heappop,heappush
import sys

dx=[0,0,1,-1]
dy=[1,-1,0,0]

N,M=map(int,input().split())

room=[list(map(int,input().split()))for _ in range(N)]
visited=[[[sys.maxsize]*2 for _ in range(M)]for _ in range(N)]
visited[0][0][0]=room[0][0]
q=[]
heappush(q,[0,0,0])


answer=1e9

while q:
    x,y,use=heappop(q)
    level=visited[x][y][use]

    for d in range(4):
        nx=x+dx[d]
        ny=y+dy[d]

        if nx<0 or nx>=N or ny<0 or ny>=M:
            continue
        now_level=max(room[nx][ny],level)
        if visited[nx][ny][use]>now_level:
            visited[nx][ny][use]=now_level
            heappush(q,[nx,ny,use])

        if use==0:
            nx+=dx[d]
            ny+=dy[d]

            if nx < 0 or nx >= N or ny < 0 or ny >= M:
                continue

            now_level = max(room[nx][ny], level)
            if visited[nx][ny][use+1]>now_level:
                visited[nx][ny][use+1] = now_level
                heappush(q, [ nx, ny, use+1])

print(min(visited[N-1][M-1]))

이것이 정답 코드입니다.
그리고 아래는 정답코드랑 정말 비슷한
오답코드를 보여드리겠습니다.

#백준 14948번 군대탈출하기
from heapq import heappop,heappush


dx=[0,0,1,-1]
dy=[1,-1,0,0]

N,M=map(int,input().split())

room=[list(map(int,input().split()))for _ in range(N)]
visited=[[[1e9]*2 for _ in range(M)]for _ in range(N)]
visited[0][0][0]=room[0][0]
q=[]
heappush(q,[room[0][0],0,0,0])


answer=1e9

while q:
    level,x,y,use=heappop(q)


    for d in range(4):
        nx=x+dx[d]
        ny=y+dy[d]

        if nx<0 or nx>=N or ny<0 or ny>=M:
            continue
        now_level=max(room[nx][ny],level)
        if visited[nx][ny][use]<=now_level:
            continue
        visited[nx][ny][use]=now_level
        heappush(q,[now_level,nx,ny,use])

        if use==0:
            nx+=dx[d]
            ny+=dy[d]

            if nx < 0 or nx >= N or ny < 0 or ny >= M:
                continue

            now_level = max(room[nx][ny], level)
            if visited[nx][ny][use+1] <= now_level:
                continue
            visited[nx][ny][use+1] = now_level
            heappush(q, [now_level, nx, ny, use+1])

print(min(visited[N-1][M-1]))

아래코드로 해도
어지간한 예제는 다 통과하는데
막상 제출하면 틀렸다고 뜹니다.
이유는 q에 nx,ny의 level도 함께 넣었기 때문입니다.

이럴 경우에는

x,y에서 필요한 level값이

서로 혼동되는 문제가 생깁니다.

이렇게 되기 때문에

level은 visited[x][y]를 꺼내주는 방식으로 해야

혹시나 최신화가 되었을때의 혼동을 방지할 수 있습니다.

 

전형적인 문제였지만

이 문제를 삽질하면서

어떤 점이 막혔는지 시원하게 알아가네요.