16933: 벽 부수고 이동하기 3

풀이 시간

• 1h 8m
• 결국 히든 테케를 못찾아서 구글링함 + 시간 초과 이슈

구현 방식

• queue의 노드에 x, y, 진행 시간, 남은 벽의 개수를 저장해줌
• visit 리스트를 MAX 값으로 초기화해줌
• board[nx][ny] == 0 and visit[nx][ny][wall] > turn 이라면,
  -> 벽을 부수지 않고 이동하는 경우임
  -> visit[nx][ny][wall]에 현재 turn을 넣어줌
• board[nx][ny] == 1 and wall and visit[nx][ny][wall-1] > turn 이라면, 벽을 만나는 경우임
• • 만약 day가 1이라면 벽을 부수고 이동
    -> visit[nx][ny][wall-1]에 현재 turn을 넣어줌
    -> if문에 visit[nx][ny][wall-1] > turn 조건이 있는 이유는 중복 제거 및 최단 시간을 구해주기 위함임
• • 만약 day가 0이라면 밤이어서 벽을 부술 수 없는 경우임 (낮이 되면 벽을 부술 수 있음)
    -> 이 경우엔 현재 위치에서 대기해야하함
    -> visit 리스트를 따로 갱신하지 않고 queue에만 노드를 추가해줌

소스 코드

import sys
from collections import deque

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

N, M, K = map(int, sys.stdin.readline()[:-1].split())
board = [list(map(int, sys.stdin.readline()[:-1].strip())) for _ in range(N)]
MAX = float('inf')
visit = [[[MAX] * (K+1) for _ in range(M)] for _ in range(N)]

result = MAX
queue = deque([(0, 0, 1, K)])
visit[0][0][K] = 0

while queue:
    x, y, turn, wall = queue.popleft()
    if (x, y) == (N-1, M-1):
        result = min(result, turn)
        continue
    
    day = turn % 2
    for i in range(4):
        nx = x + dx[i]; ny = y + dy[i]
        if 0 <= nx < N and 0 <= ny < M:
            if board[nx][ny] == 0 and visit[nx][ny][wall] > turn: #벽 부수지 않고 이동
                visit[nx][ny][wall] = turn
                queue.append((nx, ny, turn+1, wall))
            elif board[nx][ny] == 1 and wall and visit[nx][ny][wall-1] > turn:
                if day: #벽 부수고 이동
                    visit[nx][ny][wall-1] = turn
                    queue.append((nx, ny, turn+1, wall-1))
                else: #밤이어서 벽을 부술 수 없는 경우 (낮이 되면 부술 수 있음)
                    queue.append((x, y, turn+1, wall))

print(result if result < MAX else -1)

결과

• 알고리즘은 같은데 bfs 탐색할 때 함수 형식으로 구현한 코드는 시간 초과가 발생하고 그냥 while문 돈 코드는 시간 초과가 발생하지 않았다