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

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

2206번: 벽 부수고 이동하기

벽 부수고 이동하기

3차원 리스트와 BFS를 활용하여 해결하는 문제

2차원으로 시도하다가 시간초과의 벽에 걸려서 다른 사람들의 코드를 참고해보니, 3차원 리스트로 풀면 해결 할 수 있는 문제였다.

정답 코드

def path_finding():
    visited = [[[0]*2 for _ in range(M)] for _ in range(N)] # 3차원 리스트, 벽 깰 때와 안 꺨 때
    visited[0][0][1] = 1 # 초기 값은 벽을 깨지 않았으니까 1
    while queue:
        y, x, wall = queue.popleft()
        for dy, dx in move:
            ny, nx = y + dy, x + dx
            if 0 <= ny < N and 0 <= nx < M:
                if maze[ny][nx] == 0 and visited[ny][nx][wall] == 0: # 이동할 수 있고, 아직 방문하지 않았으면
                    visited[ny][nx][wall] = visited[y][x][wall] + 1 # 이동하고 거리 +1
                    queue.append([ny,nx,wall])

                if maze[ny][nx] == 1 and wall == 1: #만약 벽에 만났는데 벽을 아직 안깨봤다면
                    visited[ny][nx][wall-1] = visited[y][x][wall] + 1 #벽을 깨고 이동해보고 거리 +1
                    queue.append([ny,nx,wall-1])

    if visited[N-1][M-1][wall] != 0: # 도달할 수 있으면
        return visited[N-1][M-1][wall] # 결과 반환
    else: # 없으면
        return -1 #-1 반환 


import sys
from collections import deque
N, M = map(int, sys.stdin.readline().split())
maze = [list(map(int, sys.stdin.readline().strip())) for _ in range(N)]
move = [[1,0], [-1,0], [0,1], [0,-1]]
queue = deque([[0,0,1]])
print(path_finding())

문제 요구 조건은 다음과 같다

1. 미로를 빠져 나갔을 때 최단 경로 구하기
2. 만약 가는 중에 벽을 부수고 이동하는게 더 빠르다면 1회에 한해 벽을 부술 수 있음

일반적인 미로 빠져나가 최단 경로를 구하는 문제였다면, 쉽게 BFS로 해결 했겠지만, 벽을 부수는 조건이 추가됐다.

여기서 아무 생각없이 어? 벽을 1개만 부수면 되니까 깊은복사로 복사한다음에 추가로 2중 for 문으로 탐색을 하면서 값을 찾았다가 당연하게도 시간 초과가 났다. N*M만해도 100만인데 여기서 내부 while문을 돈다면?..

문제 해결을 위해 3차원 리스트를 사용하여 경우를 나누어 주었다. 일반적인 BFS문과 동일하지만, 만약 벽을 만났는데 깨볼 수 있으면 그 루트대로 저장해주는 식으로 반복하여 도달할 수 있는지 없는지 여부를 판단해 출력하도록 작성하였다.

---

느낀 점

매번 많은 문제를 풀 때 대부분 최대 2차원 배열을 이용해서 문제를 해결 했다보니, 이 문제도 2차원 배열로 접근했다가 시간초과의 벽과 마주해서, 원하는 형태로 구현하지 못했다.

3차원 리스트로 접근하는 방법을 생각하지 조차 못했는데, 여러 문제를 해결 할 경우 무조건 2차원이 아니라 n차원의 다양한 리스트를 활용해볼 수 있단 생각이 들었다.

틀에만 박혀서 쓰던거만 쓰지 않고, 새로운 걸 떠올릴 필요가 있다는 걸 깨닫게 해준 문제가 아닌가 싶다.