[BOJ] Q2206 벽 부수고 이동하기

[BOJ] Q2206 벽 부수고 이동하기

Question

Language: Python

Difficulty: Gold 4

얼핏보면 bfs을 이용해서 경로 순회 중에 벽을 만나면 벽을 한개 부서서 다시 bfs 을 진행하고, 목적지까지 탐색하고 다시 이전 bfs으로 돌아가서 새로운 벽을 부수고, 다시 bfs을 진행해보는 식으로 bfs을 여러번 돌려보는 식으로 진행하면 문제가 풀릴것 같다.

하지만, row, column의 개수가 제법 큰 숫자이며, 이렇게 마구잡이로 bfs으로 돌리게 되면 시간 초과가 발생할 수 있다. 따라서 이럴때는 bfs을 최소한의 횟수로 돌려야된다. 그래서 이 문제는 visited을 고려할때, 벽을 부순경우와 벽을 부수지 않은 경우를 추가해서 고려한다.

visited

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

이렇게 visited[row][col][crushed] row,col 에 대해서 부순 경우와 부수지 않고 진행한 경우, 2가지에 대해 고려하고 순회를 진행한다.

Solution

from math import inf
from collections import deque

def solution():
    visited=[[[0]*2 for _ in range(m)] for _ in range(n)]
    dy=[-1,0,1,0]
    dx=[0,1,0,-1]

    queue=deque([(0,0,0)]);
    visited[0][0][0]=1
    
    while queue:
        row,col,crushed=queue.popleft()

        if row==n-1 and col == m-1:
            return visited[row][col][crushed]

        for dir in range(4):
            new_row=row+dy[dir]
            new_col=col+dx[dir]

            if new_row < 0 or new_row >=n or new_col < 0 or new_col >=m:
                continue

            if graph[new_row][new_col] ==0 and visited[new_row][new_col][crushed] == 0:
                queue.append((new_row,new_col,crushed))
                visited[new_row][new_col][crushed]=visited[row][col][crushed]+1
            
            if graph[new_row][new_col] ==1 and crushed ==0:
                queue.append((new_row,new_col,crushed+1))
                visited[new_row][new_col][crushed+1]=visited[row][col][crushed]+1
                

    return -1

if __name__ == "__main__":
    n,m=map(int,input().split())
    graph=[list(map(int,input().strip())) for _ in range(n)]
    print(solution())