백준 2206 : 벽 부수고 이동하기 [파이썬]

 

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

2206번: 벽 부수고 이동하기

 

1. 문제 설명

(0, 0) 에서 (n-1, m-1) 까지 이동할 수 있다면 거리를, 없다면  -1을 출력하는 문제인데 문제는 벽을 하나 부술 수 있다라는 것이였다.

 

1. 첫 시도

 

처음은 그냥 bfs를 시도한다.

그리고 벽을 하나씩 0으로 만들고 시도한후, 다시 1로 만든다.

bfs를 시도할때마다 (n-1, m-1)를 리스트에 넣고 최댓값을 뽑는다.

최댓값이 0이라면 못가는 곳이기에 -1을 출력한다.

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

def bfs():
    global distance
    queue = deque()
    queue.append((0,0))
    while queue:
        x, y = queue.popleft()
        if visit[x][y] > distance:
            return
        for i in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            nx = x + i[0]
            ny = y + i[1]

            if 0 <= nx < n and 0 <= ny < m and not visit[nx][ny] and not board[x][y]:
                queue.append((nx, ny))
                visit[nx][ny] = visit[x][y] + 1

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


wall = []
distance = 1e9
for i in range(n):
    for j in range(m):
        if board[i][j]:
            visit = [[0] * m for _ in range(n)]
            visit[0][0] = 1
            board[i][j] = 0
            bfs()
            if visit[n-1][m-1]:
                if distance > visit[n-1][m-1]:
                    distance = visit[n-1][m-1]
            board[i][j] = 1

if distance == 1e9:
    print(-1)
else:
    print(distance)

물론 이풀이는 시간초과에 걸린다. 매우 많은 visited를 생성해야 했고 너무 많은 탐색을 했기 때문

 

2. 정답

from collections import deque

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

visited = [[[0] * 2 for _ in range(m)] for _ in range(n)]
visited[0][0][0] = 1

dx = [0,0,1,-1]
dy = [1,-1,0,0]

def bfs(a, b, c):
    queue = deque()
    queue.append((a,b,c))

    while queue:
        x, y, z = queue.popleft()
        if x == n-1 and y == m-1:
            return visited[x][y][z]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if nx<0 or nx>=n or ny<0 or ny>=m:
                continue
            if board[nx][ny] == 1 and z == 0:
                visited[nx][ny][1] = visited[x][y][0] + 1
                queue.append((nx, ny, 1))
            elif board[nx][ny] == 0 and visited[nx][ny][z] == 0:
                visited[nx][ny][z] = visited[x][y][z] + 1
                queue.append((nx, ny, z))
    return -1

print(bfs(0,0,0))

3차원 배열로 만드는 것이 시간 초과를 해결하는 것이였다. 

visited를 삼차원으로 만들어 벽을 부술 경우와 부수지 않을 경우를 나눠서 최단 거리를 찾아내는 방식이였다.