#282 백준 파이썬 [2206] 벽 부수고 일어나기 - BFS

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

 

SOLUTION

기본적으로 BFS를 통한 미로탐색 문제와 성격이 같다.

https://www.acmicpc.net/problem/2178 문제와 https://claude-u.tistory.com/212 풀이를 보자

여기에 더하여 한 가지의 벽 알고리즘을 더 추가해준다.

 

벽 알고리즘

1) distance[N][M] 리스트를 만들어 벽에 도달했을 때 distance를 저장해준다.

2) BFS를 활용했으므로 처음으로 벽에 도달한 순간이 가장 빠르게 도달한 경우이다. 따라서 이후 distance는 필요 없으므로 visited[i][j]에 True를 대입해 더 이상 방문하지 않도록 한다.

3) 미로의 시작 지점인 0,0과 끝 지점인 N,M에서 두 번 BFS를 수행해주고 각각 distance 함수를 출력해준다.

4) 처음과 끝에서 BFS 함수를 돌린 경우, 두 distance[i][j] 함수를 각각 더해주면 0,0 ~ i,j 까지의 거리, i,j ~ N-1,M-1 까지의 거리가 나온다.

이미 뚫린 곳 뿐만 아니라 벽까지의 거리도 구해져 있으므로 벽을 뚫는 경우의 수를 포함한다.

 

5) 둘 중에 하나의 배열의 distance[i][j]가 0인경우 양쪽 도달 가능한 방법의 수가 없는 경우이므로 패스한다.

6) 배열 중 distance가 가장 적은 경우를 출력해준다.

PYTHON CODE

from collections import deque

#BFS로 미로 탈출 알고리즘 정의
def bfs(i, j):
    global maze, N, M
    queue = deque() #함수 안에서 쓰일 큐, 빠르게 deque로 정의한다
    queue.append([i, j])
    visited = [[False for _ in range(M)] for _ in range(N)] #방문 시 True로 변경
    distance = [[0 for _ in range(M)] for _ in range(N)] #부딪히는 벽을 포함한 거리를 입력
    distance[i][j] = 1 #시작일 경우 / 끝일 경우
    
    while queue: 
        [i, j] = queue.popleft()
        visited[i][j] = True #방문 완료!
        
        #일반적인 길일 경우에 큐에 넣어줌
        if i < N-1 and maze[i+1][j] == 0 and visited[i+1][j] == False and [i+1, j] not in queue:
            queue.append([i+1, j]) #큐에 추가
            distance[i+1][j] = distance[i][j] + 1 #거리 1추가
        if i > 0 and maze[i-1][j] == 0 and visited[i-1][j] == False and [i-1, j] not in queue:
            queue.append([i-1, j])
            distance[i-1][j] = distance[i][j] + 1
        if j < M-1 and maze[i][j+1] == 0 and visited[i][j+1] == False and [i, j+1] not in queue:
            queue.append([i, j+1])
            distance[i][j+1] = distance[i][j] + 1
        if j > 0 and maze[i][j-1] == 0 and visited[i][j-1] == False and [i, j-1] not in queue:
            queue.append([i, j-1])
            distance[i][j-1] = distance[i][j] + 1
        
        #벽에 부딪힐 경우, 해당 벽까지의 거리 입력
        if i < N-1 and maze[i+1][j] == 1 and visited[i+1][j] == False:
            distance[i+1][j] = distance[i][j] + 1
            visited[i+1][j] = True
        if i > 0 and maze[i-1][j] == 1 and visited[i-1][j] == False:
            distance[i-1][j] = distance[i][j] + 1
            visited[i-1][j] = True
        if j < M-1 and maze[i][j+1] == 1 and visited[i][j+1] == False:
            distance[i][j+1] = distance[i][j] + 1
            visited[i][j+1] = True
        if j > 0 and maze[i][j-1] == 1 and visited[i][j-1] == False:
            distance[i][j-1] = distance[i][j] + 1
            visited[i][j-1] = True
            
            
    return distance #distance리스트 리턴

#입력
N, M = map(int, input().split())
maze = []
for _ in range(N): #미로를 2차원 배열로 받음
    maze.append(list(map(int, str(input()))))


from_start = bfs(0,0) #시작 지점 BFS
from_end = bfs(N-1,M-1) #종결 지점 BFS
min_distance = N * M + 1 #최대치 + 1을 넣어줌

#가장 작은 거리를 출력하기 위한 이중 for문
for i in range(N):
    for j in range(M):
        if from_start[i][j] != 0 and from_end[i][j] != 0: #양쪽 도달 가능한 방법의 수가 있는 경우
            min_distance = min(from_start[i][j] + from_end[i][j] - 1, min_distance)
#출력
if min_distance == N * M + 1:
    print(-1)
else:
    print(min_distance)