[백준/14442/파이썬] 벽 부수고 이동하기 2

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

14442번: 벽 부수고 이동하기 2

Problem

• N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다.
• 맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오. 

조건

• 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.
• 만약에 이동하는 도중에 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 K개 까지 부수고 이동하여도 된다.
• 한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.

SOL

단순히, BFS를 순환하는 큐에 벽의 갯수 정보를 추가해주면 되는 문제 같았다. 하지만, 생각보다 간단한 문제가 아니였다. 이러한 반례가 발생하기 때문이다.

 

문제점

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

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

board=[list(map(int,input().rstrip())) for _ in range(N)]
visited=[[False for _ in range(M)] for _ in range(N)]
dx=[1,0,-1,0]
dy=[0,1,0,-1]
ans=1e9
flag=False
def moving(y,x,cnt,d):
    global ans,flag
    dq=deque()
    dq.append((y,x,cnt,d))
    visited[y][x] =True
    while dq:
        y,x,cnt,d = dq.popleft()
        if y==N-1 and x==M-1:
            ans=min(ans,d)
            flag=True
        for k in range(4):
            ny=y+dy[k]
            nx=x+dx[k]
            if (0<=ny<N and 0<=nx<M) and not visited[ny][nx]:
                if not board[ny][nx]:
                    dq.append((ny,nx,cnt,d+1))
                    visited[ny][nx] = True
                elif board[ny][nx]==1 and cnt<K: # 벽인 경우
                    dq.append((ny,nx,cnt+1,d+1))
                    visited[ny][nx] = True

moving(0,0,0,1)

print(ans) if flag else print(-1)

반례)

4 4 2
0110
1000
0111
0010

 

일때, BFS의 탐색 특성 상, 퍼지는 경로는 랜덤이다.(상대좌표를 어떻게 구현하냐에 따라서 달라지기 때문).

하지만, 내가 짠 코드로 진행하게 되면, 이미 방문한 지점에 벽을 2개까지 깬 경우가 오히려 손해인 경우가 있다.

(즉, 벽을 깨는게 최단거리로 갈 수 있는건 맞지만, 위처럼 마지막에 도달을 위해서 1개는 써야하는데, 2개를 깨버리면 안된다.) 말로 표현하자면, 지금까지 온 경로가 최선이더라도, 다음 경로부터는 best가 아닐 수 있다는 이야기임.(즉, local 적으로는 최선일지 몰라도, 전역적으로는 최선이 아니다)

 

• 따라서, 같은 좌표에도 내가 벽을 몇개까지 깼는지의 공간을 각각 따로 만들어야한다. 

사실, 이 문제에서는 같은 좌표라면, 벽을 적게 깬게 이득이다. 왜냐하면, 같은 좌표라도 벽을 깰 수 있는 기회를 가지고 있다면,  앞으로 단축시킬 여력이 남아있기 때문이다.

• [K][N][M]의 3차원 배열을 선언하지 않고, [N][M] 2차원 배열을 선언한 후, 벽을 깬 횟수 K보다 적은것만 방문표시를 해줘도 된다. 이러면 효율적으로 구현이 가능하다. (전체를 K+1로 초기화 한 다음, cnt와 visited[ny][nx]를 비교해주면서, 반복을 해주면 편할거다)

하지만, 이 문제에서만 그런 경우고, 난 좀 더 일반적인 풀이를 선택했다. 직접 하나하나 다 시뮬레이션 하는 경우

 

수정된 코드

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

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

board=[list(map(int,input().rstrip())) for _ in range(N)]
visited=[[[False for _ in range(M)] for _ in range(N)] for _ in range(K+1)]
dx=[1,0,-1,0]
dy=[0,1,0,-1]

def moving(y,x,cnt,d):
    dq=deque()
    dq.append((y,x,cnt,d))
    visited[0][y][x] =True
    while dq:
        y,x,cnt,d = dq.popleft()
        if y==N-1 and x==M-1:
            return d
        for k in range(4):
            ny=y+dy[k]
            nx=x+dx[k]
            if (0<=ny<N and 0<=nx<M):
                if board[ny][nx]==1 and cnt<K and not visited[cnt+1][ny][nx]:  # 벽인 경우
                    dq.append((ny,nx,cnt+1,d+1))
                    visited[cnt+1][ny][nx] = True
                elif board[ny][nx] ==0 and not visited[cnt][ny][nx]:
                    dq.append((ny,nx,cnt,d+1))
                    visited[cnt][ny][nx] = True
    return -1

print(moving(0,0,0,1))