[Baekjoon, Python] 2206번 : 벽 부수고 이동하기

도입

백준 단계별 풀기 DFS와 BFS 여덟 번째 문제이다.

백준 2206번 문제, 입력, 출력

---

백준 2206번 입출력 예제 1, 2

---

DFS와 BFS

DFS

- Root Node 혹은 다른 임의의 Node에서 이어진 Branch를 완벽하게 탐색하고 다른 이어진 Branch로 넘어가는 방법.

한 방향으로 계속 가서 끝을 마주하면 다른 방향으로 설정해서 마찬가지로 진행.

- Stack 또는 Recursive함수로 구현.

- 시간 복잡도 : 인접 리스트는 $O(V+E)$ 인접 행렬은 $O(V^2)$ // 접점(V), 간선(E)

BFS

- Root Node 혹은 다른 임의의 Node에서 이어진 Branch들의 바로 하나 건너 있는 Node들을 먼저 탐색.

- Queue로 구현

- 시간 복잡도 :  인접 리스트는 $O(V+E)$ 인접 행렬은 $O(V^2)$ // 접점(V), 간선(E)

---

풀이

1. 2178번의 미로탐색의 최단거리 문제를 풀어보았다면, 문제의 절반은 풀었다고 봐도 된다. BFS를 이용해서 푼다. 

 

2. 3차원 배열을 사용한다. 3차수의 값(z)은 0과 1로 z==0일때는, 아직 뚫지 않은 최단경로, z==1일 때는 벽을 한번 뚫은 상태의 최단경로를 의미한다.  

 

3. 입출력 예제 1의 입력을 넣었을 때 print(deque) 를 하게 되면 확인할 수 있는 그림이다. print(deque)는 bfs 함수 내부 조건문 2군데에 넣어서 진행하였다. 위의 2줄은 아랫 조건(z == 0 and mat_before[nx][ny] == 1 and mat_visit[nx][ny][z+1] == -1)의 print(deque)이고 나머지 3번째 줄부터는 첫 번째 조건(mat_before[nx][ny] == 0 and mat_visit[nx][ny][z] == -1)의 print(deque) 결과 이다. 

 

 

print(deque)

4. 입출력 예제 1의 입력을 넣었을 때 방문한 값을 저장해놓은 변수(mat_visit)의 결과를 출력하였다.

mat_visit[0][0][0] : 1    mat_visit[1][0][0] : -1   ...    mat_visit[5][0][0] : -1

mat_visit[0][0][1] : 3    mat_visit[1][0][1] : 2    ...    mat_visit[5][0][1] : 12

mat_visit[0][1][0] : -1  mat_visit[1][1][0] : -1    ...    mat_visit[5][1][0] : -1

mat_visit[0][1][1] : 2    mat_visit[1][1][1] : -1    ...    mat_visit[5][1][1] : 13

mat_visit[0][2][0] :-1    mat_visit[1][2][0] :-1    ...    mat_visit[5][2][0] : -1

mat_visit[0][2][1] : 3    mat_visit[1][2][1] : -1    ...    mat_visit[5][2][1] :14

mat_visit[0][3][0] : -1  mat_visit[1][3][0] : -1    ...    mat_visit[5][3][0] : -1

mat_visit[0][3][1] : 4    mat_visit[1][3][1] : 5    ...    mat_visit[5][3][1] : 15

mat_visit의 bfs함수 실행 전과 후

 

---

코드

from sys import stdin
from collections import deque
#import pprint

dx=[-1,0,1,0] # 좌 우 
dy=[0,1,0,-1] # 위 아래

def bfs():
    queue.append([0, 0, 0])
    mat_visit[0][0][0] = 1
    while queue:
        x, y, z = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < var_N and 0 <= ny < var_M:
                if mat_before[nx][ny] == 0 and mat_visit[nx][ny][z] == -1:  # 좌우위아래 길이고, 방문한적이 없다면,
                    mat_visit[nx][ny][z] = mat_visit[x][y][z] + 1
                    queue.append([nx, ny, z])
                    #print(queue)
                elif z == 0 and mat_before[nx][ny] == 1 and mat_visit[nx][ny][z+1] == -1: # z==0:뚫은적이 없고, 좌우위아래벽이고, 방문한적이 없다면,
                    mat_visit[nx][ny][z+1] = mat_visit[x][y][z] + 1
                    queue.append([nx, ny, z+1])
                    #print(queue)

var_N,var_M = map(int, stdin.readline().split())
mat_before = [list(map(int, input())) for _ in range(var_N)]
#mat_before = [list(map(int, stdin.readline().split())) for _ in range(var_N)]   -> why?
mat_visit = [[[-1]*2 for _ in range(var_M)] for _ in range(var_N)]
queue = deque()

bfs()
#pprint.pprint(mat_visit)
var_rtn_1, var_rtn_2 = mat_visit[var_N-1][var_M-1][0], mat_visit[var_N-1][var_M-1][1]
if var_rtn_1 == -1 and var_rtn_2 != -1:
    print(var_rtn_2)
elif var_rtn_1 != -1 and var_rtn_2 == -1:
    print(var_rtn_1)
else:
    print(min(var_rtn_1, var_rtn_2))

---

마무리

3차원 배열이라 조금 생소한 개념으로 느껴졌다. 문제를 푼 이후 다른 문제에서 마찬가지로 적용시켜보려면 익숙해지기 위한 연습이 필요할 것 같다.