BOJ 2206 _ 벽 부수고 이동하기 _ 파이썬

📃 문제

BOJ 2206 벽 부수고 이동하기

알고리즘 - BFS

3차원 BFS + 장애물

💡 풀이 과정

풀이 방법을 생각하는 과정 및 이유

1) BFS여야 하는 이유
BFS는 최단거리를 보장한다! ↔DFS는 보장할 수 없다.
도착지에 도착하는 거리를 BFS로 구하면 그게 최단거리이다.

2) 고려할 조건
이 문제에서 고려할것은 벽! 최대 한번 부수고 이동할 수 있다.
한번 부수고 가는 경우가 안부수고 가는 경우보다 빠를 수 있고, 부수는 경우가 최대 한 번인지도 고려해야한다!!

3) 3차원
맵을 3차원으로 두고 이용해야한다. 높이차원은 0과 1이 있다.
즉, 벽을 부수지 않았을 때의 2차원 배열, 벽을 부신 후의 2차원 배열 이렇게 두 차원이다. 각각 0, 1
초기=부수지않음=차원0 에서 한번 부수는 경우가 발생했으면 이후부턴 차원1에서 탐색을 이어가면 된다!

구현 과정

입력 부분

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

visited = [[[0 for _ in range(m)] for _ in range(n)] for _ in range(2)]
visited[0][0][0] =1 #시작위치

방문여부 및 거리를 담은 삼차원 배열을 선언한다. 초기엔 모두 0이고 시작위치만 1로 지정한다. 문제의 조건 중에 "이때 시작하는 칸과 끝나는 칸도 포함해서 센다." 가 있기 때문에 시작위치부터 1을 카운트 해야한다!!

BFS 동작 부분

queue = deque([(0,0,0)])
while queue:
    broken, i,j = queue.popleft()
    if i==n-1 and j == m-1:
        print(visited[broken][i][j])
        sys.exit()
    for d in range(4):
        ni = i+di[d]
        nj = j+dj[d]
        if 0<= ni < n and 0<= nj < m :
            if arr[ni][nj] == 1 and not broken: #다음이 벽(1)인데 부신적 없으면
                visited[1][ni][nj] = visited[0][i][j]+1
                queue.append((1,ni,nj))
            elif not arr[ni][nj] and not visited[broken][ni][nj]: # 다음 벽 아니면서 방문한적 없는 칸이면
                visited[broken][ni][nj] = visited[broken][i][j] +1
                queue.append((broken, ni, nj))

시작은 벽 안 부신 차원0 이고 (0,0)에서 시작한다.
queue 반복문 종료조건은 도착지에 도착할 때 이다.
도착한다면, 계산된 거리를 바로 출력하고 종료하면된다.

현재위치를 popleft를 통해 얻는다.
→ 다음위치는 상하좌우이다
-→ 다음위치가 벽(arr[ni][nj]==1)이고 아직 벽을 부시지 않았다면(broken==0) 벽을 부신차원1로 옮겨가야한다. 현재 거리에 1을 더한 값을 차원1로 준다 -> 큐에 다음위치를 넣는다
-→ 다음위치가 벽이 아니고(arr[ni][nj]==0), 방문한적 없는 칸(visited[broken][ni][nj])이면 같은 차원에서 방문거리를 1 늘려서 넣어주면된다. -> 큐에 다음위치를 넣는다

*** 그외의 경우를 따지지 않는 이유?
그 외의 경우라면,
-다음위치가 벽이고 이미 벽이 부신경우 ⇒ 더이상 부실수 없기 때문에 아무 이동을 할 수 없다.
-다음위치가 벽이 아닐때에 대해선, 이미 벽을 부셨는지 아닌지가 중요하지 않다! 기존의 BFS 사용했던 방식대로 방문했었는지 아닌지만 따지면된다. 당연히 방문했던칸이면 아무 이동이 없다.

최종 코드 😲

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

n, m =map(int,input().split())
arr = []
for _ in range(n):
    arr.append(list(map(int,list(input().rstrip()))))
visited = [[[0 for _ in range(m)] for _ in range(n)] for _ in range(2)]
visited[0][0][0] =1 #시작위치
di = [0, 1, 0 ,-1]
dj = [1, 0, -1, 0]
queue = deque([(0,0,0)]) # 맨앞:높이차원:0벽안부심/1벽부심 , i , j
while queue:
    broken, i,j = queue.popleft()
    if i==n-1 and j == m-1:
        print(visited[broken][i][j])
        sys.exit()
    for d in range(4):
        ni = i+di[d]
        nj = j+dj[d]
        if 0<= ni < n and 0<= nj < m :
            if not broken and arr[ni][nj] == 1: #다음이 벽(1)인데 부신적 없으면
                visited[1][ni][nj] = visited[0][i][j]+1
                queue.append((1,ni,nj))
            elif not arr[ni][nj] and not visited[broken][ni][nj]: # 다음 벽 아니면서 방문한적 없는 칸이면
                visited[broken][ni][nj] = visited[broken][i][j] +1
                queue.append((broken, ni, nj))
else:
    print(-1)

TMI ..

다른 맞힌 사람의 코드를 보다보면 종종 삼차원을 [x][y][벽 차원]으로 쓴다.

2차원 배열이고 각각의 값이 [ , ] 이렇게 인덱스0,1의 리스트를 가진 형식으로 쓰는 것 같다.

근데 나의 풀이처럼, 이차원 배열을 두개 가지고 있어서 각각 안부신경우(0), 부신경우(1)로 이해하려면 [벽 차원][x][y]가 맞는 것 같다.