[BAEKJOON]2206 벽 부수고 이동하기 - Python

문제 요약

• 알고리즘 분류:BFS, 시뮬레이션
• 난이도: Gold3
• 문제내용:
  • 0은 길 1은 벽이다.
  • 벽은 한번 부수고 이동가능하다.
  • (0, 0) ~ (N, M)까지의 거리를 구해라

• 사이트: https://www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

문제풀이

   이번에는 문제 유형은 그래프 탐색중에 BFS탐색 알고리즘이다. BFS 탐색 알고리즘에 대한 설명은 여기에서 확인 해보면된다.

import sys
from collections import deque
input = sys.stdin.readline
INF = 1000 * 1000

def bfs():
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]
    field = [[INF] * M for _ in range(N)]
    field[0][0] = 1
    queue = deque([(0, 0)])
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            fx, fy = x + dx[i], y + dy[i]
            if 0 <= fx < N and 0 <= fy < M and matrix[fx][fy] == 0 and field[fx][fy] == INF:
                field[fx][fy] = field[x][y] + 1
                queue.append((fx, fy))
    return field[N-1][M-1]

N, M = map(int, input().split())
matrix = []
for _ in range(N):
    array = []
    for i in input()[:-1]:
        array.append(int(i))
    matrix.append(array)

walls = []
for x in range(N):
    for y in range(M):
        if matrix[x][y] == 1:
            walls.append((x, y))

min_value = bfs()
for x, y in walls:
    matrix[x][y] = 0
    min_value = min(bfs(), min_value)
    matrix[x][y] = 1

print(-1 if min_value == INF else min_value)

 이번 문제는 가로 세로 1000이고 위 코드 처럼 브루드포스로 모든 벽을 한 번씩 부수고 탐색하면 O(N ^ 4)이상 나와서 시간 초과가 나올것이다. 

문제 접근 방법

 위 코드 처럼 모든 벽을 탐색하지말고 벽을 부수지 않고 이동하는 경우와 벽을 부수고 이동한 경우를 두 가지 경우를 동시에 탐색 할것이다. 그럼 일단 정상적으로 이동할 경우 2차원 배열과 벽을 부수고 이동하는 2차원 배열을 합쳐서 3차원 배열로 만들것이다. 

 그러면 2가지 경우만 생각하면된다. 벽을 만날경우 이전에 벽을 한번 부수고 이동하나  벽을 안 부수고 이동하나 벽을 한번도 안 부수고 온 경우에는 벽을 부수고 이동하는 배열로 이동하면 된다. 하지만 벽을 한번 부수고 이동할 경우에는 탐색 취소 시킨다. 그 외 경우는 BFS 알고리즘 처럼 하면된다.

정리

1. 기존 미로와 벽을 부수고 이동할 미로 3차원 배열을 만든다.
2. 기존 로직에 벽을 만났을때 이전 탐색한노드에서 기존 미로에서 이동한 경우와 벽을 부수고 이동한 미로에서 처리하는 로직을 추가한다.

Code

Python

import sys
from collections import deque
input = sys.stdin.readline
INF = 1000 * 1000 # 최대값

def bfs():
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]
    field = [[[INF, INF] for _ in range(M)]for _ in range(N)]
    field[0][0][0] = 1
       
    queue = deque([(0, 0, 0)])
    while queue:
        x, y, flag = queue.popleft() # x, y는 좌표 flag는 이전에 벽을 뚫었는지
        for i in range(4):
            fx, fy = x + dx[i], y + dy[i]
            if 0 <= fx < N and 0 <= fy < M:
                # 일반적인 경우
                if matrix[fx][fy] == 0 and field[fx][fy][flag] == INF:
                    field[fx][fy][flag] = field[x][y][flag] + 1
                    queue.append((fx, fy, flag))
                # 벽이 있는데 이전에 벽을 안뚫었을 경우
                elif matrix[fx][fy] == 1 and flag == 0:
                    field[fx][fy][1] = field[x][y][flag] + 1
                    queue.append((fx, fy, 1))
    result = min(field[N-1][M-1])
    return -1 if result == INF else result

N, M = map(int, input().split())
matrix = []
for _ in range(N):
    array = []
    for i in input()[:-1]:
        array.append(int(i))
    matrix.append(array)

print(bfs())