[백준] - 미로 탈출

링크

https://www.acmicpc.net/problem/14923

14923번: 미로 탈출

 

 

풀이

BFS 를 이용하여 최소 경로를 찾고

벽을 부셨는지 여부를 체크하여 해결

 

4번 제출하고 3번을 틀렸는데 이런 상황을 생각하지 못해서 틀렸다.

hx,hy = 1, 1

ex, ey = 1, 4

0 1 1 0

0 1 0 1

0 1 0 0

0 0 0 0

 

이때 BFS를 돌리면 [1, 1]의 벽을 부시고 [2, 3]으로 이동하는데 이때 이미 벽을 부셨기 때문에

더 이상 벽을 부실수가 없기 때문에 목적지로 가지 못하는 상황때문에 3번 틀리게 되었는데

해결 방법으로 다음 목적지를 확인 할때 이미 방문 하였더라도 현재 상황에서 벽을 부시지 않았다면

한번 더 이동 할 수 있도록 하였다.

 

 

 

코드

import sys
from collections import deque

INF = 123124123231
VISITED_CHECK = 0
DESTORY_BLOCK = 1
COUNT = 2

dir = [[-1, 0], [0, 1], [1, 0], [0, -1]]


def solution(*args):
    n, m, start_x, start_y, ex, ey, board = args
    check_board = [[[False, False, -1] for _ in range(m + 1)] for _ in range(n + 1)]

    dq = deque([[start_x, start_y]])
    check_board[start_x][start_y] = [True, board[start_x][start_y], 0]
    while dq:
        hx, hy = dq.popleft()
        check_board[hx][hy][VISITED_CHECK] = True
        for dx, dy in dir:
            nx, ny = hx + dx, hy + dy
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            if check_board[nx][ny][VISITED_CHECK]:
                if not check_board[nx][ny][DESTORY_BLOCK] > check_board[hx][hy][DESTORY_BLOCK]:
                    continue
            if board[nx][ny] == 1 and check_board[hx][hy][DESTORY_BLOCK]:
                continue
            check_board[nx][ny][VISITED_CHECK] = True
            check_board[nx][ny][DESTORY_BLOCK] = check_board[hx][hy][DESTORY_BLOCK]
            check_board[nx][ny][COUNT] = check_board[hx][hy][COUNT] + 1
            if board[nx][ny] == 1:
                check_board[nx][ny][DESTORY_BLOCK] = True
            dq.append([nx, ny])
            if nx == ex and ny == ey:
                return check_board[nx][ny][COUNT]
    return check_board[ex][ey][COUNT]


if __name__ == "__main__":
    n, m = map(int, sys.stdin.readline().split())
    hx, hy = map(int, sys.stdin.readline().split())
    ex, ey = map(int, sys.stdin.readline().split())
    board = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

    print(solution(n, m, hx - 1, hy - 1, ex - 1, ey - 1, board))