[boj 11206][Python] 벽 부수고 이동하기

문제 링크: https://www.acmicpc.net/problem/11206

어렵다!

벽 부수고 이동하기는 bfs에서 자주 보이는 응용 (길 찾기, 최단경로 찾기)에 하나의 요소를 더 추가한 문제이다.

이 문제에서는 길찾기 도중 벽을 딱 한 번 뚫을 수 있다. 그리고 벽을 뚫지 않으면 진행 불가능한 경우도 존재한다.

첫번째 시도

모든 벽에 대해서 그것을 뚫어놓고 bfs 수행한 결과를 리스트로 저장, 마지막엔 리스트에서 min 값을 찾아내기

예제 2개에 대해서는 작동하나, 시간 초과가 된다.

맵의 최대 크기는 1000*1000 사이즈이므로, 그 맵이 전부 벽이라고 가정하면 1000*1000회의 계산을 해야 한다.

따라서 이 방법은 일단 접근이 틀렸다.

두번째 시도

bfs를 수행하며, 벽을 이미 부쉈는지, 부수지 않았는지를 기억해야 할 것 같은데...

잘 모르겠어서 이미 푼 사람들의 포스트를 알아봄.

• Visited 배열을 벽이 부서지지 않은 상태 (=0), 벽을 이미 부순 상태 (=1) 로 나눠서 관리 (즉, 3차원 배열)
• Visited 배열을 bool 이 아니라 int 값으로 두고, 거리까지 관리.
  • 이건 처음 보는 방법이다... 원래 큐에 원소 4개를 써서 거리와 벽부숨 여부를 관리하려고 했는데, 막혀서 이런 방법으로 바꾸었다.

코드

# ㅠㅠ - 2트
# 2206 벽 부수고 이동하기

from sys import stdin
from collections import deque

input = stdin.readline

n, m = map(int, input().split())
ar = [[0] for _ in range(n)]

for i in range(n):
    ar[i] = list(map(int, list(input().rstrip())))


visited = [[[0 for _ in range(2)] for _ in range(m)] for _ in range(n)]
# 3rd elem: 0이면 부수기 가능
#           1이면 부수기 불가
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]
# elem 1st, 2nd - 좌표
# 3rd - isBroken & 거리 동시에
#   0 - 미방문, 양수 - 방문, 거리

result = -1

def bfs():
    queue = deque([(0, 0, 0)])  
    visited[0][0][0] = 1

    while queue:
        cur = queue.popleft()
        isBroken = cur[2]
        if cur[0] == n-1 and cur[1] == m-1:
            result = visited[cur[0]][cur[1]][isBroken]
            return result    # 탐색 종료
        for d in range(4):
            xx = cur[0] + dx[d]
            yy = cur[1] + dy[d]
            if 0 <= xx and xx < n and 0<= yy and yy < m and visited[xx][yy][isBroken] == 0:
                if ar[xx][yy] == 0: # 전진 가능
                    queue.append((xx, yy, isBroken))
                    visited[xx][yy][isBroken] = visited[cur[0]][cur[1]][isBroken] + 1
                else:   # 전진 불가
                    if not isBroken:   # 벽부수기 가능
                        queue.append((xx, yy, 1))
                        visited[xx][yy][1] = visited[cur[0]][cur[1]][isBroken] + 1
                    # 벽부수기 불가 - 더이상 진행 안 됨, 처리 할 것 없음.
    return -1

print(bfs())

메모

• bfs 는 기본적으로 최적(최단)의 경로를 보장한다. 굳이 결과들을 관리할 필요 없이 처음으로 나오는 result가 최적이다.
  • bfs에 있어서 기본적인 부분이지만 잠시 헷갈렸었다.
• 4방향 탐색 시, 이미 방문한 곳은 다시 방문하지 않아야 한다.
  • 이것도 bfs 기초지만 빼먹어서 조금 헛발질했다.
• rstrip 을 빼먹었을 때 - '\n'은 정수로 변환할 수 없다고 나온다.