백준 2606: 벽 부수고 이동하기 (Python)

 

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

2206번: 벽 부수고 이동하기

 

from collections import deque

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

for i in range(n):
    data = input()
    for j in range(m):
        list[i].append(int(data[j]))

def bfs(x, y, z):
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]

    queue = deque()
    queue.append([x, y, z])

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

    while queue:
        qx, qy, qz = queue.popleft()

        if qx == n-1 and qy == m-1:
            return visited[qx][qy][qz]

        for i in range(4):
            mx = qx + dx[i]
            my = qy + dy[i]

            if mx < 0 or mx >= n or my < 0 or my >= m:
                continue

            if list[mx][my] == 1 and qz == 1:
                visited[mx][my][0] = visited[qx][qy][1] + 1
                queue.append([mx, my, 0])
            elif list[mx][my] == 0 and visited[mx][my][qz] == 0:
                visited[mx][my][qz] = visited[qx][qy][qz] + 1
                queue.append([mx, my, qz])

    return -1

print(bfs(0, 0, 1))

 

처음엔 flag 변수를 하나 둬서 벽을 뚫으면 flag 값을 변하게 해서 더이상 벽을 못 뚫게 했다

근데 단순히 그렇게 하면 길이 없는 방향으로 벽을 뚫었을 때 답을 못 찾게 됨

그래서 고민을 해보다가 진짜 도저~~~~히 모르겠어서 구글링함.....

3차원 배열을 써야 한다길래 또 열심히 머리를 쥐뜯었다

전 왜 이렇게 멍청한거죠? 알고리즘이 이해가 안 가요,,,,,,,,,,

 

visited 배열을 3차원으로 두고 x, y는 각 맵의 좌표이고

여기서 z가 1이면 벽을 뚫을 수 있는 상태이고 0이면 벽을 이미 한번 뚫었기 때문에 뚫을 수 없는 상태이다. (flag 역할을 함)

bfs 돌리면서 벽을 만났고, 벽을 뚫을 수 있는 상태이면 뚫음 그리고 visited + 1

길이 있고(벽 아님), 아직 방문한 적이 없는 길이면 visited + 1

 

겨우겨우 이해했지만 아직 헷갈린다 알고리즘을 좀더 뜯어봐야 할 것 같다

 

맞은게 맞은게 아님......... python3 너무 오래걸려서 pypy3로도 돌려봤다