[Gold III] 벽 부수고 이동하기 2 - 14442

문제 링크

성능 요약

메모리: 476376 KB, 시간: 6668 ms

분류

그래프 이론, 그래프 탐색, 너비 우선 탐색, 격자 그래프

문제 설명

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.

만약에 이동하는 도중에 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 K개 까지 부수고 이동하여도 된다.

한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.

맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.

출력

첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다.

---

문제 풀이

문제 분석

N x M 크기의 맵에서 (1, 1)에서 (N, M)까지 최단 경로를 찾는 문제입니다. 맵에는 이동 가능한 곳(0)과 벽(1)이 있으며, 최대 K개의 벽을 부수고 이동할 수 있습니다. 시작점과 도착점을 포함한 최소 칸 수를 출력해야 하며, 도달할 수 없는 경우 -1을 출력합니다.

접근 방법

최단 경로를 찾는 문제이므로 너비 우선 탐색(BFS)을 사용하는 것이 적절합니다. 벽을 부수는 횟수가 제한되어 있으므로, 방문 여부를 체크할 때 단순한 2차원 배열이 아닌 3차원 배열을 사용하여 각 위치에서 벽을 부순 횟수에 따라 방문 여부를 구분해야 합니다. 3차원 배열은 visited[n][m][k+1] 형태가 됩니다. 여기서 k는 해당 위치까지 오면서 부순 벽의 개수를 나타냅니다.

구현 설명

1. 입력 및 초기화

• 입력으로 N, M, K를 받고 맵 정보를 graph 리스트에 저장합니다.
• 상하좌우 이동을 위한 directions 리스트를 정의합니다.
• 방문 여부를 저장하는 3차원 리스트 visited를 False로 초기화합니다. 크기는 [N][M][K+1]입니다.

2. BFS 탐색

• 큐에 시작 위치 (0, 0), 이동 거리 1, 부순 벽의 개수 0을 튜플 형태로 넣어줍니다. queue.append((0, 0, 1, 0))
• 큐가 빌 때까지 다음을 반복합니다.
  • 큐에서 현재 위치 (x, y), 이동 거리 cnt, 부순 벽의 개수 k_cnt를 꺼냅니다.
  • 만약 현재 위치가 (N-1, M-1)이라면 cnt를 반환합니다. (목표 지점에 도달)
  • 상하좌우 방향으로 이동합니다.
    • 새로운 위치가 맵 안에 있고, 아직 방문하지 않았다면 다음을 수행합니다.
      • 만약 이동하려는 곳이 벽이 아니고 (graph[sx][sy] == 0) 해당 k_cnt로 방문한 적이 없다면 visited[sx][sy][k_cnt]를 True로 설정하고 큐에 (sx, sy, cnt+1, k_cnt)를 추가합니다.
      • 만약 이동하려는 곳이 벽이고 (graph[sx][sy] == 1) k_cnt가 K보다 작고 해당 k_cnt+1로 방문한 적이 없다면 visited[sx][sy][k_cnt+1]를 True로 설정하고 큐에 (sx, sy, cnt+1, k_cnt+1)를 추가합니다. (벽을 부수고 이동)

3. 불가능한 경우 처리

• BFS 탐색이 종료되었는데도 목표 지점에 도달하지 못했다면 -1을 반환합니다.

4. 결과 출력

• BFS 함수의 반환값을 출력합니다.

⏱복잡도 분석

• 시간 복잡도: BFS의 시간 복잡도는 일반적으로 O(V+E)입니다. 여기서 V는 정점의 수, E는 간선의 수입니다. 이 문제에서는 맵의 크기가 N x M이고, 각 위치에서 최대 4방향으로 이동할 수 있으며, 벽을 부수는 횟수가 K번까지 가능하므로 시간 복잡도는 O(N * M * K * 4) = O(NMK)가 됩니다.
• 공간 복잡도: graph 리스트는 O(N * M)의 공간을 사용하고, visited 3차원 리스트는 O(N * M * K)의 공간을 사용합니다. 큐는 최악의 경우 맵의 모든 위치를 저장할 수 있으므로 O(N * M * K)의 공간을 사용할 수 있습니다. 따라서 전체 공간 복잡도는 O(NMK)입니다.

핵심 포인트

1. 3차원 방문 배열: 벽을 부수는 횟수를 고려하여 3차원 배열을 사용하여 방문 여부를 체크해야 합니다.
2. BFS 활용: 최단 경로를 찾는 문제이므로 BFS를 사용하는 것이 효율적입니다.
3. 벽 부수기 조건: 벽을 부술 때마다 K값을 확인하여 K번 초과로 벽을 부수지 않도록 해야 합니다.

풀이 코드

import sys
from itertools import combinations
from collections import deque

input = sys.stdin.readline

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

graph= []

for i in range(n):
    graph.append(list(map(int, input().strip())))

directions = [(1,0),(-1,0),(0,1),(0,-1)]

visited = [[[False] * (k+1) for i in range(m)] for i in range(n)]

def BFS():
    queue = deque()
    queue.append((0,0,1,0))

    while queue:
        visited[0][0][0] = True
        x,y,cnt,k_cnt = queue.popleft()

        if x == n-1 and y == m-1:
            return cnt

        for dx,dy in directions:
            sx,sy = x+dx,y+dy
            if 0<=sx<n and 0<=sy<m:
                if not visited[sx][sy][k_cnt] and graph[sx][sy] == 0:
                    visited[sx][sy][k_cnt] = True
                    queue.append((sx,sy,cnt+1,k_cnt))

                if k_cnt < k and not visited[sx][sy][k_cnt+1] and graph[sx][sy] == 1:
                    visited[sx][sy][k_cnt+1] = True
                    queue.append((sx,sy,cnt+1,k_cnt+1))

    return -1
        
print(BFS())