악곱 == 악성곱슬

BFS

---

이 문제는 BFS인데 그냥 일반적으로 벽을 하나씩 제거해보는 방식으로 완전 탐색을 하게 되면 O((N*M)^2)이 된다. 따라서 100만의 제곱, 즉 시간초과가 발생한다.

따라서 새로운 방식의 접근이 필요하다. 3차원 리스트으로 graph를 확장시킨다. 만약 벽을 뚫었으면 1 아직 뚫지 않았으면 0. 이렇게 해서 2개의 층을 이용해서 bfs를 구현하는 방식이다. 모르면 생각해내기 어려운 문제이므로 이렇게 풀 수도 있다는 것을 기억해놓자.

코드는 아래와 같다.

import sys
from collections import deque
import copy

dn = [-1, 1, 0, 0]  # 상, 하, 좌, 우
dm = [0, 0, -1, 1]

def bfs(start, n, m):
    q = deque()
    q.append(start)
    visited = [[[0]*2 for _ in range(m)] for _ in range(n)]
    visited[0][0][0] = 1
    while q:
        now_x, now_y, wall = q.popleft()
        if now_x == n-1 and now_y == m-1:
            return visited[now_x][now_y][wall]
        for i in range(4):
            nn = now_x + dn[i]
            nm = now_y + dm[i]
            # 인덱스 벗어남
            if nn < 0 or nm < 0 or nn >= n or nm >= m:
                continue
            # 벽을 만나면 뚫고 차원이동, wall 이 0이라는 것은 아직 뚫지 않았다는 점
            if graph[nn][nm] == 1 and wall == 0:
                visited[nn][nm][1] = visited[now_x][now_y][0] + 1
                q.append((nn, nm, 1))
            # 그냥 일반 길을 만났을 때.
            if graph[nn][nm] == 0 and visited[nn][nm][wall] == 0:
                visited[nn][nm][wall] = visited[now_x][now_y][wall] + 1
                q.append((nn, nm, wall))
    return -1

def solution(n, m):
    answer = bfs((0, 0, 0), n, m)
    print(answer)

if __name__ == "__main__":
    N, M = map(int, sys.stdin.readline().rstrip().split())
    graph = list()
    for _ in range(N):
        data = list(map(int, sys.stdin.readline().rstrip()))
        graph.append(data)
    solution(N, M)