[알고리즘] 백준2206 벽 부수고 이동하기 - 파이썬

이번 문제는 단계별 풀기 bfs, dfs파트에 7번째 문제인 벽 부수고 이동하기 문제입니다. 

 

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

2206번: 벽 부수고 이동하기

 

 

풀이 코드

# 벽을 하나 부쉴 수 있다는 점
# 불가능이면 -1
# 최단거리 = bfs
from collections import deque
from sys import stdin

n, m = map(int, stdin.readline().split())

graph = []
for _ in range(n):
    graph.append(list(map(int, stdin.readline().strip())))
# print("bfs 적용 전",visit)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs():
    queue = deque()
    queue.append([0, 0, 1])
    visit = [[[0] * 2 for _ in range(m)] for _ in range(n)]
    visit[0][0][1] = 1 # 벽을 한번 부술 수 있는 상태에서 시작

    while queue:
        x, y, w = queue.popleft()
        if x == n-1 and y == m-1:
            return visit[x][y][w]
        for i in range(4):
            xx = x + dx[i]
            yy = y + dy[i]
            if 0 <= xx < n and 0 <= yy < m:
                if graph[xx][yy] == 1 and w == 1: # 벽을 만나고 벽을 한번 부술 수 있는 경우
                    visit[xx][yy][0] = visit[x][y][w] + 1
                    queue.append([xx, yy, 0])
                elif graph[xx][yy] == 0 and visit[xx][yy][w] == 0: # 벽이 없고 방문한적이 없는 경우
                    visit[xx][yy][w] = visit[x][y][w] + 1
                    queue.append([xx, yy, w])
    return -1

print(bfs())
# print("bfs 적용 후",visit)

 

문제풀이

: 3차원 배열로 푸는 문제가 아직까지는 어려운 것 같습니다. visit배열을 따로 만들어 방문 여부를 체크해주는 동시에 visiti [][][i]에서 i가 1인 경우는 벽을 부술 수 있는 상태, 0인 경우는 벽을 한번 부 순상태로 나누어 푸는 문제입니다. 이해가 가지 않아 밑에 분의 블로그를 참고했습니다.  

 

https://pacific-ocean.tistory.com/348

[백준] 2206번(python 파이썬)