[boj] 22944_죽음의 비_python

문제링크

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

22944번: 죽음의 비

---

문제설명

입력

1. 정사각형 격자의 한변의 길이인 N, 현재 체력 H, 우산의 내구도 D가 공백으로 주어진다.

2~N+1 :  정사각형 격자의 정보가 N개의 문자로 붙어서 주어진다.

 

- 주어지는 문자

우산은 "U", 현재 있는 위치 "S", 안전지대 "E", 빈 칸 "."만 존재한다.
현재 있는 위치 "S"와 안전지대 "E"는 반드시 1개 존재

 

출력

안전지대로 이동할 때 최소 이동 횟수( 이동하지 못할 경우 -1 출력 )

제한

•  4 ≤ N ≤ 500
•  0 ≤ K ≤ 10
• 1 ≤ H ≤ 10,000
•  1 ≤ D ≤ 5,000
• 주어지는 모든 수는 정수이다.

---

문제풀이

입력 시간 복잡도 : visited O(N²) + rainOfDeath O(N²) => O(N²)

출력 시간 복잡도 : 1. BFS 초기위치 O(N²) + 2. bfs 탐색 O(N²) * 3. 상하좌우 탐색 O(4) => O(N²)

공간 복잡도 : visited O(N²)  + rainOfDeath O(N²)  + XY O(4) + player O(5N) => O(N²) 

 

BFS를 통해 상하좌우를 탐색하되

visited가 방문 여부만이 아닌, 방문 지점에서의 현재 체력과 비교하여 결정한다.

 

이유?

                # 현재 요소로 방문 처리
                if visited[pX][pY] < pH:
                    visited[pX][pY] = pH
                    player.extendleft([(pX, pY, pH, pU, pCnt+1)])

만약 단순히 bool 배열로 방문 여부만 체크한다면 체력이 더 적어 이미 다른 곳을 방문하였던 효율적이지 않은 경로가 저장될 수 있기 때문에 이를 방지하기 위해 위와 같은 처리를 해주었다.

 

---

import sys # 빠른 입력을 위함
from collections import deque # bfs 사용을 위함
def solution():
    # 이동 범위 지정
    XY = [ [-1,0], [1,0],[0,-1], [0,1]]
    # 빠른 입력
    input = sys.stdin.readline
    # N : 가로세로 길이 H : 현재 체력 D: 내구도
    N, H, D = map(int, input().split())
    # 초기 배열 입력
    rainOfDeath = [list(input().strip('\n')) for _ in range(N)]
    # 방문 여부 배열, 각 지점에서의 체력을 저장함
    visited = [[0 for _ in range(N)] for _ in range(N)]
    # 남은 우산 체력
    cost = 0
    # 이동 횟수
    cnt = 0
    # 1. BFS 초기 위치 (S의 위치)
    player = deque()
    x, y = 0,0
    for i in range(N):
        for j in range(N):
            if rainOfDeath[i][j] == 'S':
                x, y = i,j
                break
    player.extend([(x, y, H, cost, cnt)])
    visited[x][y] = H  # 시작점 방문 처리
    # 2. bfs 탐색
    while player:
        posX, posY, pHP, pUM, pCnt = player.pop()# 상하좌우 탐색
        # 3. 상하좌우 탐색
        for dx, dy in XY:
            pX, pY = posX + dx, posY + dy
            pH,pU = pHP, pUM
            if 0<= pX < N and 0<= pY < N:
                # E : 도착시 최소 이동 횟수 출력하기
                if rainOfDeath[pX][pY] == 'E':
                    print(pCnt+1)
                    return
                # U : 우산일 경우 우산 내구도 D로 갱신
                if rainOfDeath[pX][pY] == 'U':
                    pU = D

                # 체력 깎아주기
                # 우산 내구도 > 0 일 경우 우산 내구도 깎아주기
                if pU > 0: pU -= 1
                # 우산 내구도 == 0 and 체력 > 0 일 경우 체력 깎아주기
                else: pH -= 1

                # 체력 == 0 : 다시 탐색
                if pH == 0: continue

                # 현재 요소로 방문 처리
                if visited[pX][pY] < pH:
                    visited[pX][pY] = pH
                    player.extendleft([(pX, pY, pH, pU, pCnt+1)])
    # 방문 실패한 경우 -1 출력
    print(-1)
solution()

 

---

참고 레퍼런스

1. https://westmino.tistory.com/97

2. https://record-developer.tistory.com/163