벽 부수고 이동하기

solved_ac[Class4][벽 부수고 이동하기](https://www.acmicpc.net/problem/2206)

문제

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.

만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다.

한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.

맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.

출력

첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다.

예제 입력 1

6 4
0100
1110
1000
0000
0111
0000

예제 출력 1

15

예제 입력 2

4 4
0111
1111
1111
1110

예제 출력 2

-1

문제 해석

[백준]1260번: DFS와 BFS의 업그레이드 문제이다. 앞서 풀었던 미로찾기와 비슷한데 여기서 추가된 것은 벽을 한번은 뚫을 수 있다는 것이다. 무조건 한번을 뚫어야 되는 것이 아닌 필요에 의해서 뚫을수도 있고 안뚫을수도 있다는 얘기이다. 이게 많이 복잡하다. 여기서 key 포인트는 벽을 안뚫고 갈때와 벽을 뚫고 갈때를 구분해서 작성을 해야 된다는 것이다. 그리고 또한 미로찾기에서는 graph를 직접 업데이트 해가면서 마지막 배열의 값이 총 걸리는 거리를 의미했는데 여기서는 graph를 직접 업데이트 시켜주면 안된다. 방문한 곳의 숫자가 증가해 있어서 이걸 벽으로 보고 못 지나갈 수 있기 때문에 다른 리스트를 이용하여 업데이트 시켜줘야한다. 그리고 또한 정답을 출력할 때 visited 리스트를 루프를 돌아 0이 아닌 리스트를 찾아 맨 마지막 리스트의 값을 출력할 필요가 없다. 어차피 최단 경로이기 때문에 bfs 루프를 돌다가 queue에서 가장 먼저 popleft()가 되어 나오는 좌표가 맨 오른쪽 밑의 좌표와 같다면 그것이 가장 최단 경로의 좌표인 것이다. 하지만 bfs 루프를 전부 돌았는데도 아무것도 return이 되는 것이 없다면 끝의 좌표에 도달하지 못한것이기 때문에 -1을 return 해주면서 정답을 도출해내면 된다.

3차원 배열

• 벽을 뚫는 경우와 벽을 뚫지 않는 경우 2가지로 나누어서 풀려고 하면 3차원 배열을 이용하는것이 효율적이다. 물론 2차원 배열 2개를 선언해서 풀어도 되지만 그렇게 되면 if문을 남발해야한다. broken이라는 flag를 세워서 만약 벽을 깼다면과 벽을 깨지 않았다면으로 따로 나누어서 2차원 리스트에 넣어줘야 하기 때문이다. 하지만 3차원 리스트로 풀게되면 flag를 세워서 조건을 따로 걸지 않고 index로 접근을 하면 된다.

선언 방식

distance = [[[0 for k in range(4)] for j in range(3)] for i in range(2)]

print(distance)

[
    [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]], 
    [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
]

혹은

distance=[[[0]*4]*3]*2

print(distance)

[
    [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]], 
    [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
]

맨 마지막에 곱해준 배열이 층이라고 생각하면 편하다.

하지만 문제에서는 맨 마지막에 2개를 벽을 뚫은 경우와 벽을 뚫지 않은 경우로 나누지 않고 맨 앞에 배열 2개로 하였다. 그 이유는 바로 쌍으로 구분하기 위해서이다.

풀이

• visited라는 3차원 배열 선언
• 처음 시작하는 점부터 거리를 1로 치기 때문에 벽을 부쉈을때의 경우와 부수지 않은 경우 첫 출발 값을 1로 준다.
• 상, 하, 좌, 우를 검색할 것이기 때문에 dx와 dy를 선언
• bfs 함수 선언
  • queue가 빌때까지 루프
    - 좌표 x, y와 벽을 부쉈는지 아닌지를 판단해 줄 인덱스인 broken 변수를 queue에서 빼낸다.
    - 초기값은 0, 0, 0이다. 0이 벽을 부수지 않은 index이다.
    - 만약 좌표가 인덱스의 제일 마지막에 다가가면
    - 가장 가까운 경로가 나왔다는 것이기 때문에 3차원 배열의 마지막 값을 return
    - 상, 하, 좌, 우를 검색하기 위해 4번 루프
    - 각 방향에 맞는 좌표를 nx와 ny로 업데이트 하면서 index의 범위에 벗어났는지 검사를 한다.
    - 만약 nx와 ny가 index 범위 내에 있다면?
    - graph[nx][ny]의 값이 1이고 broken이 0이라면?
    - 이 뜻은 벽이면서 한번도 벽을 부순적이 없다면?과 같은 뜻이다.
    - 벽을 부순 index는 1이기 때문에 3차원 배열에서 벽을 부순 경우에 값을 넣어준다.
    - 이렇게 되면 벽을 중간에 부쉈을 때 앞에 값들은 다 0이지 않나?
    - 상관없다. 어차피 이전에 갔던 길은 가지 않기 때문이다.
    - 가더라도 우리가 결국 확인해야 할 것은 마지막 좌표이기 때문이다.
    - 그러고 업데이트한 nx와 ny 그리고 broken을 1로 넣어준다. 벽을 부쉈기 때문
    - 만약 nx, ny 좌표에 벽이 없고, 해당 좌표에 들른적이 없다면?
    - 통과할수 있기 때문에 거리 값을 그 전 거리값에 1 높여서 넣어준다.
    - 그리고 해당 좌표와 broken 변수를 queue에 집어넣어준다.
    queue가 빌 때까지 다 돌렸는데도 끝 좌표에 다가가지 못했으면 결국 경로가 없다는 것이기 때문에 -1을 리턴해준다.

import sys
from collections import deque

N, M = map(int, sys.stdin.readline().split())

graph = [[0 for _ in range(M)] for _ in range(N)]

queue = deque()
queue.append([0, 0, 0])

for i in range(N):
    graph[i] = list(map(int, sys.stdin.readline().rstrip()))

visited = [[[0] * 2 for _ in range(M)] for _ in range(N)]
visited[0][0][0] = 1
visited[0][0][1] = 1

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

def bfs():
    while queue:
        x, y, broken = queue.popleft()
        if x == N - 1 and y == M - 1:
            return visited[x][y][broken]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx >= 0 and nx < N and ny >= 0 and ny < M:
                if graph[nx][ny] == 1 and broken == 0:
                    visited[nx][ny][1] = visited[x][y][0] + 1
                    queue.append([nx, ny, 1])
                elif graph[nx][ny] == 0 and visited[nx][ny][broken] == 0:
                    visited[nx][ny][broken] = visited[x][y][broken] + 1
                    queue.append([nx, ny, broken])
    return -1
        
non_broken = False
broken = False

print(bfs())

고찰

3차원 배열에 대해서 전혀 알지 못하는 상태여서 초반에 많이 고전했다. 처음에 풀고 싶었던 방식은 broken이라는 flag 변수를 세워서 queue값에 위의 코드처럼 같이 넣어주고 만약 flag가 벽을 부순 flag이면 앞으로 벽을 못부수게 0만 찾아서 찾아가는식으로 코드를 짯다. 그런데 문제점이 위에서는 graph를 직접 업데이트 안하고 visited라는 리스트를 따로 만들어서 업데이트를 해줬는데 나는 graph를 직접 업데이트 해가면서 검사를 했기 때문에 갈 수 있는 경로인데도 숫자가 있으면 벽이라고 생각해서 못가는 반례가 나왔다.