BOJ 2206 벽 부수고 이동하기

https://www.acmicpc.net/problem/2206
시간 2초, 메모리 192MB
input :

• N M (1 <= N, M <= 1,000)
• 1, 0 으로 구성된 맵(1은 이동할 수 없는 벽, 0은 이동 가능)
• (1, 1), (N, M)은 항상 0

output :

• 최단 거리를 출력, 불가능 할 때는 -1을 출력.

조건 :

• 최단 경로는 시작하는 칸과 끝나는 칸도 포함해서 센다.
• 한 개의 벽을 부수고 이동하는 것이 더 경로가 짧아진다면, 한 개 까지는 부수고 이동하여도 된다.
• 이동 할 수 있는 칸은 상하좌우.

기저사례를 생각해보자.

• 벽을 2번 이상 깨야 하는 경우.
• 현재의 위치가 목적지일 떄 값을 저장.

칸을 한 칸 씩 이동할 때 마다 값을 저장 해놓을 값이 필요
목적지에선 최솟값을 비교해서 저장해야함.

현재 까지 이동한 거리를 기록하는 새로운 지도가 필요

import sys
sys.setrecursionlimit(1000000)

N, M = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(N)]
dp = [[] for _ in range(N)]
result = 100000000
cnt = 1

for i in range(N):
    data = sys.stdin.readline().strip()
    for j in data:
        graph[i].append(int(j))
        dp[i].append(int(j))

def DFS(x, y, crash):
    global result
    global cnt


    if x == N - 1 and y == M - 1:
        result = min(result, cnt)

    dx = [1, -1, 0, 0]
    dy = [0, 0, -1, 1]

    for i in range(len(dx)):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx >= N or nx < 0 or ny < 0 or ny >= M:
            continue
        if graph[nx][ny] == 1:
            if crash:
                continue
            else:
                crash += 1
                cnt += 1
                graph[x][y] = 2

                DFS(nx, ny, crash)

                graph[x][y] = dp[x][y]
                cnt -= 1
                crash -= 1

        elif graph[nx][ny] == 0:
            cnt += 1
            graph[x][y] = 2

            DFS(nx, ny, crash)

            graph[x][y] = dp[x][y]
            cnt -= 1

DFS(0, 0, 0)
if result == 100000000:
    print(-1)
else:
    print(result)

DFS로 풀고 있었는데 메모리 초과가 발생한다... BFS 찾아보자.
dp로 그려놓는 메모리가 큰것 같다.

대부분 3차원 배열을 이용하는데. 어떤 여부를 저장해 놓으려는 경우에 자주 쓰는 것 같다.
벽을 뚫을 수 있는 능력 존재
존재 하지 않음 두 경우를 나눠서 저장 해놓는 배열이 있으니 매우 편하다.

import sys
from _collections import deque

N, M = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(N)]
cache = [[[0] * 2 for _ in range(M)] for _ in range(N)]

for i in range(N):
    data = sys.stdin.readline().strip()
    for j in data:
        graph[i].append(int(j))

def BFS():
    q = deque([(0, 0, 1)])
    cache[0][0][1] = 1

    while q:
        x, y, crash = q.popleft()
        if x == N - 1 and y == M - 1:
            return cache[N - 1][M - 1][crash]
        dx = [1, -1, 0, 0]
        dy = [0, 0, -1, 1]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx >= N or nx < 0 or ny >= M or ny < 0:
                continue
            if graph[nx][ny]:
                if crash and not cache[nx][ny][crash - 1]:
                    cache[nx][ny][crash - 1] = cache[x][y][crash] + 1
                    q.append((nx, ny, crash - 1))
                else:
                    continue
            else:
                if not cache[nx][ny][crash]:
                    cache[nx][ny][crash] = cache[x][y][crash] + 1
                    q.append((nx, ny, crash))
ret = BFS()
if ret:
    print(ret)
else:
    print(-1)

3차원 배열 잘 써먹어 보자