벽 부수고 이동하기 ( 2206번 )

2206번 제출

 

나의 풀이

from collections import deque
import sys

def _main(n, m, map_list, og_map, ch_map):
    queue = deque([(0, 0, 0, 1)]) # x, y, crush_type, cost
    og_map[0][0] = 1

    while queue:
        x, y, crush_type, cost = queue.popleft()
        if (x == (n - 1)) and (y == (m - 1)):
            return cost

        for m_x, m_y in ((1, 0), (-1 ,0), (0, 1), (0, -1)):
            n_x, n_y = (m_x + x), (m_y + y)
            if (0 <= n_x < n) and (0 <= n_y < m):
                if (map_list[n_x][n_y] == 0):
                    if (crush_type == 0):
                        if not og_map[n_x][n_y]:
                            og_map[n_x][n_y] = True
                            queue.append((n_x, n_y, crush_type, cost + 1))
                    else:
                        if not ch_map[n_x][n_y]:
                            ch_map[n_x][n_y] = True
                            queue.append((n_x, n_y, crush_type, cost + 1))

                else:
                    if (crush_type == 0) and (not ch_map[n_x][n_y]):
                        ch_map[n_x][n_y] = True
                        queue.append((n_x, n_y, 1, cost + 1))
    return -1


n, m = map(int, sys.stdin.readline().rstrip().split())
map_list, og_map, ch_map = [], [], []
for _ in range(n):
    map_list.append(list(map(int, sys.stdin.readline().rstrip())))
    og_map.append([False] * m)
    ch_map.append([False] * m)

print(_main(n, m, map_list, og_map, ch_map))

 

시간 복잡도

_main(n, m, map_list, og_map, ch_map) : 이차형 배열을 탐색하며 최단거리 return ( 이차형 시간 복잡도 )
해당 알고리즘 시간복잡도 : 이차형 시간 복잡도 ( O(n ** 2) )