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

💡문제

백준 2206번 문제 링크

🍀풀이

이 문제의 핵심은 벽을 한번 부술 수 있다는 것이다.
우선 BFS 코드를 작성을 하고 벽을 어떻게 하면 부술 수 있을까 생각을 하면서 이것저것 시도를 해봤는데 안돼서 다른 사람 코드를 참고를 했다.
그랬더니 방문배열을 3차원 배열로 해서 벽을 부쉈는지의 여부를 체크해서 하는거였다... 우진오빠가 저번에 코테리뷰하면서 3차원배열로 했던걸 봤었는데 아주 유용한 것이었네...

코드

import sys
from collections import deque
input = sys.stdin.readline

n, m = map(int, input().split())
graph = [list(map(int, input().rstrip())) for _ in range(n)]

# 방문여부를 체크 하는 배열(벽 부순 여부를 추가하여 3차원 배열로 설정)
visited = [[[0] * 2 for _ in range(m)] for _ in range(n)]

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

def bfs():
    queue = deque()
    queue.append((0, 0, 0))
    visited[0][0][0] = 1
    
    while queue:
        x, y, b = queue.popleft()
        
        # 목표 지점 도달했으면 거리 리턴
        if x == n-1 and y == m-1:
            return visited[x][y][b]
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                
                # 벽이 없고, 방문할 수 있는 경우
                if graph[nx][ny] == 0 and visited[nx][ny][b] == 0:
                    queue.append((nx, ny, b))
                    visited[nx][ny][b] = visited[x][y][b] + 1
                    
                # 벽이 있고, 아직 벽을 부수지 않은 경우
                elif graph[nx][ny] == 1 and b == 0:
                    queue.append((nx, ny, 1))
                    visited[nx][ny][1] = visited[x][y][b] + 1
                
    return -1

print(bfs())

이런식으로 해서 해결했다! 이번에도 새로운걸 배워갑니다... 이걸 생각해서 또 써먹을 수 있을진 모르겠지만 ㅠㅠ