2206: 벽 부수고 이동하기 && 14442: 벽 부수고 이동하기2

2206: 벽 부수고 이동하기

• visit 리스트를 3차원으로 선언하여 벽을 부쉈는 지, 부수지 않았는 지의 두 가지 경우를 확인해줘야하는 게 이 문제의 포인트였다
• queue에 노드를 넣어줄 때, [X, Y, wall]을 넣어주어 벽을 부쉈는 지, 부수지 않았는 지를 기록해줌
• "board[nextX][nextY] == 1 and visit[nextX][nextY][wall] and wall == 0" 인 경우는 벽을 아직 부수지 않은 상태이며, 다음 경우에 벽을 부수고 지나가는 경우임 -> 해당 경우의 child node부터는 wall이 1로 바뀜

import sys
from collections import deque

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

def bfs():
    queue = deque([])
    queue.append([0, 0, 0])
    visit[0][0][0] = 1

    while queue:
        currX, currY, wall = queue.popleft()
        if currX == N-1 and currY == M-1:
            print(visit[currX][currY][wall])
            return
        for i in range(4):
            nextX = currX + dx[i]; nextY = currY + dy[i]
            if 0 <= nextX < N and 0 <= nextY < M:
                if board[nextX][nextY] == 0 and visit[nextX][nextY][wall] == 0: #벽 부수지 않는 경우
                    visit[nextX][nextY][wall] = visit[currX][currY][wall] + 1
                    queue.append([nextX, nextY, wall])
                elif board[nextX][nextY] == 1 and visit[nextX][nextY][wall] == 0 and wall == 0: #벽 부수는 경우
                    visit[nextX][nextY][1] = visit[currX][currY][wall] + 1
                    queue.append([nextX, nextY, 1])
    print(-1)
        

N, M = map(int, sys.stdin.readline()[:-1].split())
board = []
for n in range(N):
    board.append(list(map(int, list(sys.stdin.readline()[:-1]))))

visit = [[[0, 0] for _ in range(M)] for _ in range(N)] # visit 리스트를 3차원으로 선언하여 벽을 부쉈는지, 부수지 않았는 지의 두 가지 경우를 check
bfs()

14442: 벽 부수고 이동하기 2

• visit 리스트의 가장 낮은 차원의 크기를 K+1로 수정해준 후 wall < K일 경우에 벽을 부순다고 생각하여 진행한 결과 시간 초과가 발생했다
• "visit[nextX][nextY][wall+1] == 0"의 조건을 추가하여 해결했다
  -> 해당 위치가 이미 벽을 부수고 지나간 위치인지를 확인해주어 중복되는 경우를 제거해줘야한다

import sys
from collections import deque

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

def bfs():
    queue = deque([])
    queue.append([0, 0, 0])
    visit[0][0][0] = 1

    while queue:
        currX, currY, wall = queue.popleft()
        if currX == N-1 and currY == M-1:
            print(visit[currX][currY][wall])
            return
        for i in range(4):
            nextX = currX + dx[i]; nextY = currY + dy[i]
            if 0 <= nextX < N and 0 <= nextY < M:
                if board[nextX][nextY] == 0 and visit[nextX][nextY][wall] == 0: #벽 부수지 않는 경우
                    visit[nextX][nextY][wall] = visit[currX][currY][wall] + 1
                    queue.append([nextX, nextY, wall])
                elif board[nextX][nextY] == 1 and wall < K and visit[nextX][nextY][wall+1] == 0: #벽 부수는 경우
                    visit[nextX][nextY][wall+1] = visit[currX][currY][wall] + 1
                    queue.append([nextX, nextY, wall+1])
    print(-1)
        

N, M, K = map(int, sys.stdin.readline()[:-1].split())
board = []
for n in range(N):
    board.append(list(map(int, list(sys.stdin.readline()[:-1]))))

visit = [[[0 for _ in range(K+1)] for _ in range(M)] for _ in range(N)] # visit 리스트를 3차원으로 선언하여 벽을 부쉈는지, 부수지 않았는 지의 두 가지 경우를 check
bfs()