[백준] 2206번 벽 부수고 이동하기 (Python)

정답 코드 및 풀이는 맨 아래에 있습니다.

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

 

• 구상이 상당히 힘들었다. 시간을 꽤나 사용한 것 같다. 난이도가 꽤 있었던 bfs문제이다.

---

< 벽 부수고 이동하기 > 

[문제]

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을 출력한다.

예제 입력	예제 출력
6 4 0100 1110 1000 0000 0111 0000	15
4 4 0111 1111 1111 1110	-1

---

틀린 아이디어

처음에는 입력받은 보드에 바로바로 방문처리하면서 접근하려 했다. 하지만 그렇게 되면 벽인지 벽이 아닌지 인식을 못하였고, 틀린 알고리즘이라는 것을 알았다.

그 후 바꾼 알고리즘이 변하지 않는 참조용 board를 만드는 것이다. 또, 방문처리 및 날짜 계산하는 board는 따로 두었다. 이렇게 하니 얼핏 맞는 것 같았다. 아래 코드처럼 작성하였다.

틀린 코드와 틀린 이유

from collections import deque

n, m = map(int, input().split())
# refBoard : 변하지 않는 초기 보드.(참조용)
refBoard = []
# board : 방문처리용
board = []
for _ in range(n):
    refBoard.append(list(map(int, input())))
for i in range(n):
    for j in range(m):
        if refBoard[i][j] == 1:
            # 벽은 -1
            refBoard[i][j] = -1
for i in range(n):
    board.append(refBoard[i][:])
direction = [(-1, 0), (1, 0), (0, -1), (0, 1)]

def bfs():
    queue = deque()
    queue.append((0, 0, True))
    board[0][0] = 1
    while queue:
        nowRow, nowCol, crashable = queue.popleft()
        for dx, dy in direction:
            nextRow = nowRow + dx
            nextCol = nowCol + dy
            if nextRow >= n or nextRow < 0 or nextCol >= m or nextCol < 0:
                continue
            # 아직 방문하지 않았다면 방문
            if board[nextRow][nextCol] == 0:
                board[nextRow][nextCol] = board[nowRow][nowCol] + 1
                queue.append((nextRow, nextCol, crashable))
            # 벽인데 아직 부서지지 않았다면 부숴서 접근
            elif refBoard[nextRow][nextCol] == -1 and crashable:
                board[nextRow][nextCol] = board[nowRow][nowCol] + 1
                queue.append((nextRow, nextCol, False))
bfs()
if board[n - 1][m - 1] == 0:
    print(-1)
else :
    print(board[n - 1][m - 1])

이렇게 하면 벽을 부수고 이미 접근했다면, 벽을 부수지 않고 뒤늦게 접근하는 것이 불가능하다. 이미 벽을 부숴서 더 빠르게 접근했기 때문에 뒤늦게 접근할 필요가 없다고 말할 수 있겠지만 아니다. '아직 벽을 부술 수 있나 없나'의 정보는 굉장히 중요한 정보이다. 같은 위치여도 벽을 부술 수 있는 상태에서의 거리와 벽을 부술 수 없는 상태에서의 거리는 모두 저장되어야 한다.

예를 들면 다음과 같은 지도에서 틀린 결과가 나온다.

6 4 0000 1110 0000 0111 1111 0000

2행 1열의 벽을 부수고 3행 1열의 점에 이미 방문을 했기 때문에, 0을 따라 빙빙 돌아서 3행 1열에 도착하여도 방문할 수 없게 된다. 그렇게 되면 벽을 이미 부순 상태의 정보만 남아있게 되고 0을 따라가다 보면 목적지에 도착을 할 수 없게 된다.

새로운 아이디어

부서진 상태의 방문처리용 board와 아직 부서지지 않은 상태의 방문처리용 board를 만드는 것이다.

풀이 및 코드

from collections import deque

n, m = map(int, input().split())
# refBoard : 변하지 않는 초기 보드.(참조용)
refBoard = []
# board[0] : 아직 깨지지 않은 것의 방문처리용
# board[1] : 한 번 깨진 것의 방문처리용
board = [[], []]
for _ in range(n):
    refBoard.append(list(map(int, input())))
for i in range(n):
    for j in range(m):
        if refBoard[i][j] == 1:
            # 벽은 -1
            refBoard[i][j] = -1
for i in range(n):
    board[0].append(refBoard[i][:])
    board[1].append(refBoard[i][:])
direction = [(-1, 0), (1, 0), (0, -1), (0, 1)]

def bfs():
    queue = deque()
    queue.append((0, 0, 0))
    board[0][0][0] = 1
    board[1][0][0] = 1
    while queue:
        crashed, nowRow, nowCol = queue.popleft()
        for dx, dy in direction:
            nextRow = nowRow + dx
            nextCol = nowCol + dy
            # 예외 처리
            if nextRow >= n or nextRow < 0 or nextCol >= m or nextCol < 0:
                continue
            # 벽일 때
            if refBoard[nextRow][nextCol] == -1:
                # 아직 부서지지 않았을 때, 벽을 부숴서 방문처리. (부쉈기 때문에 board[1]에 방문처리)
                if not crashed:
                    board[1][nextRow][nextCol] = board[0][nowRow][nowCol] + 1
                    queue.append((1, nextRow, nextCol))
            # 벽이 아닐 때
            else :
                # 아직 방문하지 않았다면 방문
                if board[crashed][nextRow][nextCol] == 0:
                    board[crashed][nextRow][nextCol] = board[crashed][nowRow][nowCol] + 1
                    queue.append((crashed, nextRow, nextCol))

bfs()
# ans1, ans2중 작은값이 답임. (둘 중 하나가 0이면 0이 아닌 값이 답)
ans1, ans2 = board[0][n - 1][m - 1], board[1][n - 1][m - 1]
ans = min(ans1, ans2)
if ans == 0:
    ans = max(ans1, ans2)
    if ans == 0:
        ans = -1
print(ans)

주석으로 충분한 설명이 들어갔으리라 믿고 마무리하겠다.

후기

이 문제는 생각을 많이 하게 하는 문제였다. 굉장히 사고력 향상 및 알고리즘 공부에 큰 도움이 되었던 것 같다. 사실 예전에 한 번 풀어봤던 문제였다. 다시 풀고 나서 예전 풀이를 보았는데 이번에 작성한 것이랑 굉장히 비슷한 결과가 나왔다. 

남들보다 꽤 빠른 시간인 2624ms가 나와서 기분이 좋다 ㅎㅎ