백준 | [파이썬 Python] 2206 벽 부수고 이동하기

문제 제목이 참 재밌다 벽 부수고 이동이라

현실적으로는 쉽지만 코드로 구현하기 어려웠다ㅠ

 

---

문제

 

 

코드

from collections import deque

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

def bfs():
    visit = [[[0]*2 for _ in range(M)] for _ in range(N)]
    visit[0][0][0] = 1
    while q:
        x,y, wall = q.popleft()
        if x == N-1 and y == M-1:
            return visit[x][y][wall]
        for k in range(4):
            xx = x + dx[k]
            yy = y + dy[k]
            if 0<= xx < N and 0<= yy < M and visit[xx][yy][wall] == 0:
                if maze[xx][yy] == 0:
                    visit[xx][yy][wall] = visit[x][y][wall] + 1
                    q.append([xx, yy, wall])
                if wall == 0 and maze[xx][yy] == 1:
                    visit[xx][yy][1] = visit[x][y][0] + 1
                    q.append([xx,yy,1])
    return -1

N, M = map(int,input().split())
maze = [list(map(int,input())) for _ in range(N)]
q = deque()
q.append([0,0,0])
print(bfs())

 

 

설명

3차원 배열을 만들어서 벽을 체크 하는 응용력이 필요한 문제이다

visit을 통해서 방문한 경로를 체크해서 시간을 줄이고 완전 탐색을 통해서 해결하면 된다