백준 2206 벽부수고이동하기/ 벽부수고이동하기2

문제 태그

• 벽부수고 이동하기1
• 벽부수고 이동하기2

문제 해설

벽을 부순 상태를 배열에 추가 해주었습니다.
통상 이차원 배열 BFS 문제를 풀때 이차원 배열로 방문 체크를 하고 최단거리 계산을 합니다.
기존 이차원배열에서 벽을 부순 상태를 추가 해주었습니다.

즉 벽을 하나 부술수 있는 경우
[][][] 이고
벽을 두개 부술수 있는 경우
[][][][] 입니다.
이를 고려 하여 코드를 짜면 됩니다.

visit = [[[0]*(K+1) for _ in range(M)] for _ in range(N)]

그리고 벽부수고이동하기 2에서
다차원 배열 방문 체크 확인을 안하여 TLE를 맞았습니다.
해당 코드 부분은 벽부수고2 주석을 확인하시면 됩니다.

if mapping[nx][ny] == 1 and crach < K and visit[nx][ny][crach+1] == 0:

🧑‍💻배운 것
상태를 고려할 땐 배열에 추가 해야한다.

###############################################
벽부수고이동하기1
###############################################
from collections import deque


def BFS(x, y, z):
    queue = deque()
    queue.append((x, y, z))
    visit[0][0][0] = 1
    while queue:
        x, y, crach = queue.popleft()
        if x == N - 1 and y == M-1:
            return visit[x][y][crach]
        for dx, dy in di:
            nx, ny = dx + x, dy + y
            if nx < 0 or ny < 0 or nx >= N or ny >= M: continue
            if mapping[nx][ny] == 1 and crach == 0:
                visit[nx][ny][1] = visit[x][y][0] + 1
                queue.append((nx, ny, 1))
            elif mapping[nx][ny] == 0 and visit[nx][ny][crach] == 0:
                visit[nx][ny][crach] = visit[x][y][crach] + 1
                queue.append((nx,ny,crach))
    return -1

N, M = map(int, input().split())
mapping = [list(map(int, input())) for _ in range(N)]
visit = [[[0]*2 for _ in range(M)] for _ in range(N)]
di = [(1, 0), (-1, 0), (0, 1), (0, -1)]
print(BFS(0, 0, 0))

################################################
벽부수고이동하기2
################################################
from collections import deque
import sys; input = sys.stdin.readline

def BFS(x, y, z):
    queue = deque()
    queue.append((x, y, z))
    visit[0][0][0] = 1
    while queue:
        x, y, crach = queue.popleft()
        if x == N - 1 and y == M-1:
            return visit[x][y][crach]
        for dx, dy in di:
            nx, ny = dx + x, dy + y
            if nx < 0 or ny < 0 or nx >= N or ny >= M: continue
            if mapping[nx][ny] == 1 and crach < K and visit[nx][ny][crach+1] == 0: # 방문을 했는 지 체크 해주셔야 합니다.
                visit[nx][ny][crach+1] = visit[x][y][crach] + 1
                queue.append((nx, ny, crach+1))
            elif mapping[nx][ny] == 0 and visit[nx][ny][crach] == 0:
                visit[nx][ny][crach] = visit[x][y][crach] + 1
                queue.append((nx,ny,crach))
    return -1

N, M, K = map(int, input().split())
mapping = [list(map(int, input().rstrip())) for _ in range(N)]
visit = [[[0]*(K+1) for _ in range(M)] for _ in range(N)]
di = [(1, 0), (-1, 0), (0, 1), (0, -1)]
print(BFS(0, 0, 0))