[Gold V] 공주님을 구해라! - 17836

문제 링크

성능 요약

메모리: 34984 KB, 시간: 64 ms

분류

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

문제 설명

용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1,1)으로 들어왔다. 마왕은 용사가 공주를 찾지 못하도록 성의 여러 군데 마법 벽을 세워놓았다. 용사는 현재의 가지고 있는 무기로는 마법 벽을 통과할 수 없으며, 마법 벽을 피해 (N, M) 위치에 있는 공주님을 구출해야만 한다.

마왕은 용사를 괴롭히기 위해 공주에게 저주를 걸었다. 저주에 걸린 공주는 T시간 이내로 용사를 만나지 못한다면 영원히 돌로 변하게 된다. 공주님을 구출하고 프러포즈 하고 싶은 용사는 반드시 T시간 내에 공주님이 있는 곳에 도달해야 한다. 용사는 한 칸을 이동하는 데 한 시간이 걸린다. 공주님이 있는 곳에 정확히 T시간만에 도달한 경우에도 구출할 수 있다. 용사는 상하좌우로 이동할 수 있다.

성에는 이전 용사가 사용하던 전설의 명검 "그람"이 숨겨져 있다. 용사가 그람을 구하면 마법의 벽이 있는 칸일지라도, 단숨에 벽을 부수고 그 공간으로 갈 수 있다. "그람"은 성의 어딘가에 반드시 한 개 존재하고, 용사는 그람이 있는 곳에 도착하면 바로 사용할 수 있다. 그람이 부술 수 있는 벽의 개수는 제한이 없다.

우리 모두 용사가 공주님을 안전하게 구출 할 수 있는지, 있다면 얼마나 빨리 구할 수 있는지 알아보자.

입력

첫 번째 줄에는 성의 크기인 N, M 그리고 공주에게 걸린 저주의 제한 시간인 정수 T가 주어진다. 첫 줄의 세 개의 수는 띄어쓰기로 구분된다. (3 ≤ N, M ≤ 100, 1 ≤ T ≤ 10000)

두 번째 줄부터 N+1번째 줄까지 성의 구조를 나타내는 M개의 수가 띄어쓰기로 구분되어 주어진다. 0은 빈 공간, 1은 마법의 벽, 2는 그람이 놓여있는 공간을 의미한다. (1,1)과 (N,M)은 0이다.

출력

용사가 제한 시간 T시간 이내에 공주에게 도달할 수 있다면, 공주에게 도달할 수 있는 최단 시간을 출력한다.

만약 용사가 공주를 T시간 이내에 구출할 수 없다면, "Fail"을 출력한다.

---

문제 풀이

문제 분석

이 문제는 N x M 크기의 성에서 (1, 1)에서 (N, M)까지 최단 시간 내에 도달해야 하는 문제입니다. 성에는 벽(1)과 빈 공간(0)이 있으며, 특별한 위치(2)에는 검 "그람"이 있습니다. 그람을 얻으면 벽을 통과할 수 있으며, T 시간 내에 공주를 구출해야 합니다. 만약 T 시간 내에 구출할 수 없다면 "Fail"을 출력하고, 가능하다면 최단 시간을 출력합니다.

접근 방법

이 문제는 너비 우선 탐색 (BFS) 알고리즘을 사용하여 해결할 수 있습니다. BFS는 최단 거리를 찾는 데 효과적인 알고리즘입니다. 두 가지 경로를 고려해야 합니다.

1. 그람을 얻지 않고 공주에게 도달하는 경로
2. 그람을 얻은 후 공주에게 도달하는 경로

두 경로 모두 BFS를 사용하여 탐색하고, 제한 시간 T 내에 도달할 수 있는 최단 시간을 찾아야 합니다. 그람을 얻었을 때와 얻지 않았을 때 방문 여부를 구분하기 위해 visited 배열을 사용하는 것이 일반적이지만, 여기서는 그람을 얻는 시점을 기준으로 이후 경로를 계산하는 방식을 사용하여 메모리를 효율적으로 사용하고 있습니다.

구현 설명

1. 입력 처리 및 초기화

• 입력으로 성의 크기 N, M, 제한 시간 T를 받고, 성의 구조를 2차원 배열 graph에 저장합니다.
• BFS 탐색을 위한 directions 배열을 정의합니다 (상, 하, 좌, 우 이동).

2. BFS 탐색

• BFS() 함수를 정의합니다.
• visited 배열을 초기화하고, 큐에 시작 위치 (0, 0)과 이동 횟수 0을 넣습니다.
• sword 변수를 None으로 초기화합니다. 이 변수는 그람을 획득했을 때, 그람을 획득한 시점부터 공주까지의 최단 거리를 저장합니다.
• 큐가 빌 때까지 다음을 반복합니다.
  • 큐에서 현재 위치 (x, y)와 이동 횟수 cnt를 꺼냅니다.
  • 만약 cnt가 t보다 크다면, 제한 시간을 초과했으므로 탐색을 중단합니다.
  • 현재 위치가 (N-1, M-1)이라면, 즉 공주 위치에 도달했다면, 다음과 같이 처리합니다.
    • sword 값이 있다면 sword 값과 현재 cnt 값 중 더 작은 값을 반환합니다.
    • sword 값이 없다면 현재 cnt 값을 반환합니다.
  • 상, 하, 좌, 우 방향으로 이동하며 다음 조건을 만족하는 경우 큐에 추가합니다.
    • 새로운 위치가 성의 범위를 벗어나지 않고 아직 방문하지 않은 위치여야 합니다.
    • 만약 새로운 위치의 값이 0 (빈 공간)이라면, visited 배열을 업데이트하고 큐에 추가합니다.
    • 만약 새로운 위치의 값이 2 (그람)이라면, visited 배열을 업데이트하고 그람을 획득한 시점부터 공주까지의 최단 거리를 계산하여 sword 변수에 저장합니다.

3. 그람 획득 후 최단 거리 계산

• 만약 sword 값이 존재하고, 그 값이 t보다 작거나 같다면 sword 값을 반환합니다.

4. 실패 처리

• 만약 큐가 빌 때까지 공주에게 도달하지 못했다면 "Fail"을 반환합니다.

⏱복잡도 분석

• 시간 복잡도: BFS의 시간 복잡도는 일반적으로 O(V + E)입니다. 여기서 V는 정점의 수이고 E는 간선의 수입니다. 이 문제에서 정점은 성의 각 칸이고, 간선은 각 칸에서 상, 하, 좌, 우로 이동할 수 있는 경로입니다. 따라서 시간 복잡도는 O(N * M)입니다. 최악의 경우 성의 모든 칸을 방문해야 하므로 O(N*M)입니다.
• 공간 복잡도: visited 배열의 크기는 O(N * M)이고, 큐의 크기는 최악의 경우 O(N * M)이 될 수 있습니다. 따라서 공간 복잡도는 O(N * M)입니다.

핵심 포인트

1. BFS를 활용한 최단 거리 탐색: 문제 해결의 핵심은 BFS를 사용하여 시작점에서 공주까지의 최단 거리를 찾는 것입니다.
2. 그람 획득 여부에 따른 분기 처리: 그람을 획득했을 때와 획득하지 않았을 때를 나누어 최단 거리를 계산해야 합니다. 이 코드에서는 그람 획득 후 공주까지의 거리를 별도로 계산하여 저장하고, 마지막에 비교합니다.
3. 시간 제한 조건 고려: T 시간 내에 공주를 구출해야 하므로, BFS 탐색 중에 시간 제한을 초과하는 경우 탐색을 중단해야 합니다.

풀이 코드

import sys
from collections import deque

input = sys.stdin.readline

n,m,t = map(int, input().split())
graph = []

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

directions = [(0,1),(0,-1),(1,0),(-1,0)]
def BFS():
    visited = [[False] * m for i in range(n)]
    queue = deque()
    queue.append((0,0,0))
    visited[0][0] = True
    sword = None
    while queue:
        x,y,cnt = queue.popleft()
        if cnt > t:
            break
            
        if x == n-1 and y == m-1:
            if sword:
                return min(sword, cnt)
            
            return cnt
        
        for dx,dy in directions:
            sx,sy = x+dx, y+dy
            if 0<=sx<n and 0<=sy<m and not visited[sx][sy]:
                if graph[sx][sy] == 0:
                    visited[sx][sy] = True
                    queue.append((sx,sy,cnt+1))
                elif graph[sx][sy] == 2:
                    visited[sx][sy] = True
                    sword = abs(sx-n+1) + abs(sy-m+1) + cnt + 1

    if sword:
        if sword <= t:
            return sword
    return "Fail"

print(BFS())