Python-2206-벽 부수고 이동하기

벽 부수고 이동하기 click

 

두 달 동안 고통받았던 문제를 (힌트를 조금 얻긴 했지만)오늘 드디어 풀 수 있었다.

기본적인 컨셉은 이해하고 있었는데, 시간초과의 벽에 부딛혀 힘들어 했었다.

기본 BFS를 별 생각없이 너무 많이 풀다보니, 내 코드에 틀을 정해놓고 적용시키는 느낌이 든다. 유연한 사고를 방해하는 원인인 것 같다. 알파벳 문제도 그렇고 조금 더 높은 난이도의 문제를 풀며 응용력을 키워나가야 겠다.

 

문제 분석

 

맵에서 0은 이동할 수 있는 곳을 나타내고 1은 이동할 수 없는 벽이 있는 곳을 나타낸다.

다른 BFS문제와 다른 점은 벽을 한 번 부수고 이동할 수 있다는 것이다.

 

이때, 벽을 부쉈는지 혹은 부수지 않았는지에 상관 없이 최단거리로 도달하는 경우를 구해야 한다.

 

BFS를 진행하며 현재 좌표까지 점을 부수고 왔는지, 부수지 않고 왔는지 판단했다. 벽을 부순 경우에는 벽을 부순 경우의 좌표들끼리 거리를 비교해나가고, 벽을 부수지 않은 경우에는 부수지 않은 좌표들끼리 거리를 비교했다.

 

이를 위해 거리를 저장하는 3차원 배열을 한 개 생성했다. 각 좌표의 0번째 index에는 벽을 부수지 않고 이동한 최단거리, 1번째 index에는 벽을 부수고 이동한 최단거리를 저장했다. 최단거리를 갱신해 나갈 계획이기 때문에 초기값은 파이썬 정수 최대값으로 설정했다.

 

[설명을 위해 예제 입력을 조금 변형했다.]

input:
5 4
0000
1110
0000
0111
0000

answer : 8

 

 

BFS를 진행하며 deque에 추가할 때, 해당 좌표까지 도달하는데 벽을 부순 적이 있는지에 대한 정보도 담아주었다.

 

deque.append((1, x, y)) - 벽을 이미 부순 경우 1을 넣어준다.

deque.append((0, x, y)) - 벽을 한 번도 부수지 않은 경우 0을 넣어준다.

 

• 벽을 부순 경우
  • 다음으로 이동할 좌표에 벽이 없을 경우에만 방문할 좌표의 0번째 index에 값을 업데이트하고, 이동
• 벽을 부수지 않은 경우
  • 다음으로 이동할 좌표에 벽이 있는 경우, 방문할 좌표의 1번째 index에 값을 업데이트하고, 이동
  • 다음으로 이동할 좌표에 벽이 없는 경우, 방문할 좌표의 0번째 index에 값을 업데이트하고, 이동

 

현재 좌표까지 벽을 부쉈는지, 부수지 않았는지를 판단해 진행할 수 있는지 없는지를 판단한다.

+ 다음으로 이동할 좌표에 저장되어 있는 거리보다 현재 이동한 거리가 같거나 크다면, 탐색을 종료한다.(deque에 append하지 않는다.)

 

위의 방법으로 탐색을 하면, 거리 정보가 저장된 3차원 배열에는 다음과 같이 정보가 저장되게 된다. 

우리는 우하단의 좌표까지 최단거리를 구해야 함으로, min(14, 8)이 정답이다.

3차원 배열로 거리 저장(벽을 부순 경우 & 부수지 않은경우)

Code

import sys
from collections import deque
read=sys.stdin.readline
inf = sys.maxsize
n,m = map(int,read().split())
MAP = list(list(int(i) for i in read().strip()) for _ in range(n))

def BFS():
    check = list(list([inf,inf] for _ in range(m)) for _ in range(n))

    point = deque([(0,0,0)])  #break wall, x, y
    check[0][0] = [1,inf]

    while point:
        b_w, a, b = point.popleft()
        for x,y in [(1,0),(0,1),(-1,0),(0,-1)]:
            ax, by = a+x, b+y
            if 0<=ax<n and 0<=by<m:
                if b_w == 0:
                    if MAP[ax][by] and check[ax][by][1] > check[a][b][0]+1:
                        check[ax][by][1] = check[a][b][0]+1
                        point.append((1, ax, by))

                    elif MAP[ax][by]==0 and check[a][b][0]+1<check[ax][by][0]:
                        check[ax][by][0] = check[a][b][0]+1
                        point.append((0, ax, by))

                elif b_w == 1 and MAP[ax][by]==0 and check[a][b][1]+1<check[ax][by][1]:
                    check[ax][by][1] = check[a][b][1]+1
                    point.append((1, ax, by))

    answer = min(check[-1][-1])
    if answer == inf:
        print(-1)
    else:
        print(answer)
BFS()

 

 

틀린 부분이 있을 수 있습니다. 피드백 주시면 고치도록 하겠습니다! 감사합니다.👍

[꼭 다시 풀어보기]