[Python] 백준 2206번 "벽 부수고 이동하기" (DFS/BFS)

문제

문제 풀이

• 벽을 뚫은 경우와 뚫지 않은 경우를 구별하기 위해 방문여부 3차원 배열로 확인
• 0인 경우 벽을 아직 뚫지 않은 상태, 1인 경우 벽을 이미 뚫은 상태
• 벽이 없는 경우 이동 횟수를 카운트 해서 방문배열에 넣고, 벽이 있으나 부술 수 있는 경우, 벽의 값을 1로 업데이트 한 후, 이동횟수 업데이트 그 후, 큐에 이동 할 위치와 벽의 값 큐에 삽입
• 목표 좌표에 도달 한 경우 이동횟수 리턴
• 탐색을 진행 했으나,  목표 지점에 도달 불가능 한 경우 -1 리턴

코드

from collections import deque
n, m = map(int,input().split())
graph = []
# 벽을 부순 상태와 부수지 않은 상태 구별하기 위해 3차원배열
visited = [[[0] * 2 for _ in range(m)] for _ in range(n)]
for _ in range(n):
    graph.append(list(map(int,input().strip())))
dy = [0, 0, -1, 1]
dx = [1, -1, 0, 0]
def bfs():
    queue = deque()
    # 0은 안부순거, 1은 부순거
    # 맨 첫 출발위치의 좌표(0,0)과
    # 벽을 부수지 않은 상태 0 큐에 삽입
    queue.append((0,0,0))
    # 방문한 좌표 visited 1로 바꿔주기
    visited[0][0][0] = 1

    while queue:
        y, x, w = queue.popleft()
        # 마지막 좌표에 도달 후 visited값 반환
        if y == n -1 and x == m - 1:
            return visited[y][x][w]
        # 상하좌우 탐색
        for i in range(4):
            new_y = y + dy[i]
            new_x = x + dx[i]
            # 이동할 수 있을 때
            if 0 <= new_y < n and 0 <= new_x < m and not visited[new_y][new_x][w]:
                # 벽을 뚫지 않고 이동할 수 있는 경우
                if graph[new_y][new_x] == 0 and visited[new_y][new_x][w] == 0:
                    visited[new_y][new_x][w] = visited[y][x][w] + 1
                    queue.append((new_y, new_x, w))
                # 벽을 뚫고 이동해야 하고, 벽을 뚫을 수 있는 상태일 때
                elif graph[new_y][new_x] == 1 and w == 0:
                    visited[new_y][new_x][w + 1] = visited[y][x][w] + 1
                    queue.append((new_y, new_x,w + 1))
    # 탐색을 진행했는데 끝까지 도달 불가한 경우 -1출력
    return -1

print(bfs())

• 만약 벽을 10번 뚫을 수 있다고 조건이 주어지면
• 벽을 10번동안 뚫는 상태를 저장해야 하므로,
• visited에 [0] * 11을 해서 벽을 하나씩 뚫어가면서 구해주면 된다.