[Gold I] 달이 차오른다, 가자. - 1194

문제 링크

성능 요약

메모리: 35436 KB, 시간: 80 ms

분류

그래프 이론, 그래프 탐색, 너비 우선 탐색, 비트마스킹, 격자 그래프

문제 설명

지금 민식이가 계획한 여행은 달이 맨 처음 뜨기 시작할 때 부터, 준비했던 여행길이다. 하지만, 매번 달이 차오를 때마다 민식이는 어쩔 수 없는 현실의 벽 앞에서 다짐을 포기하고 말았다.

민식이는 매번 자신의 다짐을 말하려고 노력했지만, 말을 하면 아무도 못 알아들을 것만 같아서, 지레 겁먹고 벙어리가 되어버렸다. 결국 민식이는 모두 잠든 새벽 네시 반쯤 홀로 일어나, 창 밖에 떠있는 달을 보았다.

하루밖에 남지 않았다. 달은 내일이면 다 차오른다. 이번이 마지막기회다. 이걸 놓치면 영영 못간다.

영식이는 민식이가 오늘도 여태것처럼 그냥 잠 들어버려서 못 갈지도 모른다고 생각했다. 하지만 그러기엔 민식이의 눈에는 저기 뜬 달이 너무나 떨렸다.

민식이는 지금 미로 속에 있다. 미로는 직사각형 모양이고, 여행길을 떠나기 위해 미로를 탈출하려고 한다. 미로는 다음과 같이 구성되어져있다.

• 빈 칸: 언제나 이동할 수 있다. ('.')
• 벽: 절대 이동할 수 없다. ('#')
• 열쇠: 언제나 이동할 수 있다. 이 곳에 처음 들어가면 열쇠를 집는다. ('a', 'b', 'c', 'd', 'e', 'f')
• 문: 대응하는 열쇠가 있을 때만 이동할 수 있다. ('A', 'B', 'C', 'D', 'E', 'F')
• 민식이의 현재 위치: 빈 곳이고, 민식이가 현재 서 있는 곳이다. ('0')
• 출구: 달이 차오르기 때문에, 민식이가 가야하는 곳이다. 이 곳에 오면 미로를 탈출한다. ('1')

달이 차오르는 기회를 놓치지 않기 위해서, 미로를 탈출하려고 한다. 한 번의 움직임은 현재 위치에서 수평이나 수직으로 한 칸 이동하는 것이다.

민식이가 미로를 탈출하는데 걸리는 이동 횟수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, 문에 대응하는 열쇠가 없을 수도 있다. '0'은 한 개, '1'은 적어도 한 개 있다. 열쇠는 여러 번 사용할 수 있다.

출력

첫째 줄에 민식이가 미로를 탈출하는데 드는 이동 횟수의 최솟값을 출력한다. 만약 민식이가 미로를 탈출 할 수 없으면, -1을 출력한다.

---

문제 풀이

문제 분석

주어진 미로에서 민식이가 시작 위치('0')에서 출구('1')까지 이동하는 최소 이동 횟수를 구하는 문제입니다. 미로에는 빈 칸('.'), 벽('#'), 열쇠('a''f'), 문('A''F')이 존재합니다. 열쇠를 획득하면 해당 열쇠에 대응하는 문을 열 수 있습니다. 만약 출구에 도달할 수 없으면 -1을 출력해야 합니다.

접근 방법

이 문제는 너비 우선 탐색(BFS) 알고리즘과 비트마스킹을 사용하여 해결할 수 있습니다.

• BFS: 최단 거리를 찾는 문제이므로 BFS가 적합합니다.
• 비트마스킹: 획득한 열쇠 정보를 효율적으로 관리하기 위해 비트마스킹을 사용합니다. 열쇠가 6개이므로, 각 열쇠의 보유 여부를 6비트로 표현할 수 있습니다. 예를 들어, 'a'와 'c' 열쇠를 가지고 있다면 0b101 (5)로 표현됩니다.

구현 설명

1. 입력 및 초기화

• 미로의 크기(N, M)를 입력받고, 미로 정보를 graph 리스트에 저장합니다.
• visited 3차원 리스트를 생성하여 방문 여부를 관리합니다. visited[i][j][k]는 (i, j) 위치에서 k개의 열쇠를 가진 상태로 방문했는지 여부를 나타냅니다. 여기서 k는 비트마스크 값입니다.
• 시작 위치('0')를 찾고, 해당 위치를 빈 칸('.')으로 변경합니다.
• BFS 탐색을 위한 큐를 생성하고, 시작 위치, 초기 열쇠 상태(0), 이동 횟수(0)을 큐에 넣습니다.

2. BFS 탐색

• 큐가 빌 때까지 다음을 반복합니다.
  • 큐에서 현재 위치(x, y), 열쇠 상태(k), 이동 횟수(cnt)를 꺼냅니다.
  • 현재 위치에서 상하좌우로 이동합니다.
    • 이동 가능한 조건:
      • 미로 범위 내에 있고 (0 <= sx < n and 0 <= sy < m)
      • 방문하지 않았고 (not visited[sx][sy][k])
      • 벽이 아니어야 합니다 (graph[sx][sy] != "#").
    • 이동 가능한 경우에 따라 다음과 같이 처리합니다.

3. 칸 종류에 따른 처리

• 빈 칸('.'): 큐에 다음 위치, 현재 열쇠 상태, 이동 횟수 + 1을 넣고, 방문 처리합니다.
• 출구('1'): 이동 횟수 + 1을 반환합니다 (최단 거리 발견).
• 열쇠('a'~'f'): 해당 열쇠를 획득합니다.
  • 획득한 열쇠에 해당하는 비트를 1로 설정합니다.
  • 새로운 열쇠 상태로 방문하지 않았다면, 큐에 다음 위치, 새로운 열쇠 상태, 이동 횟수 + 1을 넣고, 방문 처리합니다.
• 문('A'~'F'): 해당 문에 대응하는 열쇠가 있는지 확인합니다.
  • 열쇠가 있다면, 큐에 다음 위치, 현재 열쇠 상태, 이동 횟수 + 1을 넣고, 방문 처리합니다.

4. 탈출 실패

• 큐가 빌 때까지 출구를 찾지 못하면, -1을 반환합니다 (탈출 불가능).

⏱복잡도 분석

• 시간 복잡도: O(N * M * 2^K) 여기서 N은 행의 개수, M은 열의 개수, K는 열쇠의 개수(6)입니다. BFS는 최악의 경우 모든 칸을 방문하며, 각 칸에서 열쇠 상태가 2^K가지 존재할 수 있습니다. 따라서 시간 복잡도는 O(N * M * 64)입니다.
• 공간 복잡도: O(N * M * 2^K). visited 3차원 배열이 N * M * 2^K 크기를 가집니다. 따라서 공간 복잡도는 O(N * M * 64)입니다.

핵심 포인트

1. BFS 활용: 최단 거리를 구하는 문제이므로 BFS를 사용하여 효율적으로 탐색합니다.
2. 비트마스킹: 열쇠 획득 정보를 비트마스크로 관리하여 메모리 사용량을 줄이고 연산 속도를 높입니다.
3. 3차원 방문 배열: 열쇠 상태를 고려하여 방문 여부를 체크하는 3차원 배열을 사용하여 중복 방문을 방지합니다.

풀이 코드

import sys
from collections import deque

input = sys.stdin.readline

n,m = map(int, input().split())

graph = []
for i in range(n):
    graph.append(list(input().strip()))

visited = [[[False] * 64 for i in range(m)] for i in range(n)]

for i in range(n):
    for j in range(m):
        if graph[i][j] == "0":
            start_x,start_y = i,j
            graph[i][j] = "."

directions = [(1,0),(-1,0),(0,1),(0,-1)]
keys = ["a","b","c","d","e","f"]
doors = ["A","B","C","D","E","F"]

def BFS(i,j):
    queue = deque()
    queue.append((i,j,0,0))
    visited[i][j][0] = True
    while queue:
        x,y,k,cnt = queue.popleft()
        for dx,dy in directions:
            sx,sy = x+dx,y+dy
            if 0<=sx<n and 0<=sy<m and not visited[sx][sy][k] and graph[sx][sy] != "#":
                if graph[sx][sy] == ".":
                    queue.append((sx,sy,k,cnt+1))
                    visited[sx][sy][k] = True

                elif graph[sx][sy] == "1":
                    return cnt+1
                
                elif graph[sx][sy] in keys:
                    key = 1 << keys.index(graph[sx][sy])
                    new_key = k | key
                    if not visited[sx][sy][new_key]:
                        queue.append((sx,sy,new_key,cnt+1))
                        visited[sx][sy][new_key] = True

                elif graph[sx][sy] in doors:
                    if k & (1 << doors.index(graph[sx][sy])):
                        queue.append((sx,sy,k,cnt+1))
                        visited[sx][sy][k] = True

    return -1

print(BFS(start_x,start_y))