[백준_2206] 벽 부수고 이동하기 python

처음 이 문제를 봤을 때에는 매우 쉽게 느껴졌으나,

시간초과의 늪에 걸리고 말았다.

 

bfs를 돌릴 때,

큐에 넣어주는 인수에 w라는 인수를 만들어,

벽을 부쉈는지 못부쉈는지를 생각하며 나아가야 한다.

 

각각의 경우를 다 계산하려면,

시간초과에 걸리고 만다.

# n, m 입력
n, m = map(int, input().split())

# grid 설계
grid = [
    [0] * m
    for _ in range(n)
]

# grid 입력
for i in range(n):
    maps = input()
    for j in range(len(maps)):
        if maps[j] == '1':
            grid[i][j] = 1

# 함수들

# in_range(x, y)
def in_range(x, y):
    return 0 <= x and x < n and 0 <= y and y < m

# bfs()
def bfs():
    while q:
        x, y, w = q.popleft()

        # 마지막 칸이면(도착했으면),
        if x == n - 1 and y == m - 1:
            # 출력
            return visited[x][y][w]

        dxs, dys = [-1, 1, 0, 0], [0, 0, -1, 1]
        for dx, dy in zip(dxs, dys):
            # 다음 위치
            nx, ny = x + dx, y + dy
            # 다음 위치가 범위 내에 있는데
            if in_range(nx, ny):
                # 그 위치가 벽이고, 부순 적 없으면
                if grid[nx][ny] and w == 1:
                    # 방문 표시 하면서 거리까지 기록
                    visited[nx][ny][0] = visited[x][y][1] + 1
                    # 큐에 넣어주기
                    q.append((nx, ny, 0))
                # 그 위치가 벽이 아니고, 방문한 적 없으면,
                elif not grid[nx][ny] and not visited[nx][ny][w]:
                    # 방문 표시 하면서 거리까지 기록
                    visited[nx][ny][w] = visited[x][y][w] + 1
                    # 큐에 넣어주기
                    q.append((nx, ny, w))
    
    # 도착 못했으면, -1 반환
    return -1

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

# 큐 사용준비
from collections import deque
q = deque()

# 방문 기록 해 주고
visited[0][0][1] = 1
# 벽을 부수지 않은 상태(1)에서의 0, 0에서 출발
q.append((0, 0, 1))
# bfs 결과를 출력
print(bfs())