[프로그래머스] [PCCP 모의고사 #2] 보물 지도

문제

https://school.programmers.co.kr/learn/courses/15009/lessons/121690

프로그래머스

 

풀이

BFS(넓이 우선 탐색) 사용해 풀었습니다.

큐에는 (x 좌표, y 좌표, 신발 사용 여부)를 저장합니다.

visited는 3차원 배열로, 인덱스별로 [x 좌표][y 좌표][신발 사용 여부]를 의미하며 이미 지나간 자리인지 체크합니다.

4 방향을 모두 확인하며 아직 지나가지 않은 자리면서 함정이 아니라면 큐에 다음 자리를 추가합니다.

신비로운 신발을 아직 사용하지 않았다면 두 칸을 이동한 자리를 체크하여 큐에 추가합니다.

 

코드

파이썬

from collections import deque

def solution(n, m, hole):
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    
    board = [[0] * m for _ in range(n)]
    for a, b in hole:
        board[a-1][b-1] = 1

    queue = deque()
    visited = [[[False] * 2 for _ in range(m)] for _ in range(n)]
    visited[0][0][False] = True
    queue.append((0, 0, False))
    L = 0
    while queue:
        for _ in range(len(queue)):
            x, y, used = queue.popleft()
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny][used] and board[nx][ny] == 0:
                    if (nx, ny) == (n-1, m-1):
                        return L + 1
                    visited[nx][ny][used] = True
                    queue.append((nx, ny, used))
                if not used:
                    nx += dx[i]
                    ny += dy[i]
                    if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny][True] and board[nx][ny] == 0:
                        if (nx, ny) == (n-1, m-1):
                            return L + 1
                        visited[nx][ny][True] = True
                        queue.append((nx, ny, True))
        L += 1
                    
    return -1