[백준] 22944번 죽음의 비 _ Python

[초기 접근 방법]

1. 현재 위치에서 골로 이동할 수 있는지 판단한다.
2. 현재 거리와 가장 가까운 우산 u를 찾아 이동한다.
3. 1~2 과정을 반복한다.

 

[틀린 이유]

• 가장 가까운 우산으로 가는 것이 효율적이 아니다(?)

 

[생각]

bfs 문제라고 생각하지 못했다.

접근 방법이 틀린 것 같아서, 풀이를 검색하다 bfs 키워드만 보고 곰곰히 생각하다가 bfs로 다시 풀어보았다.

visited[i][j] = Boolean 으로 코드를 제출했는데 '틀렸습니다.'

"왜? 최소 경로는 bfs 맞는데??" 하고 다른 블로그를 찾아 들어가 정독해봤더니

visited[i][j]에 '남은 체력'을 저장하고 풀었어야 했다.

"맞다. bfs이므로 한쪽이 우선으로 탐색되어, 우산을 사용하는 효율적인 경로를 찾지 못한다!"

 

visited[i][j] = True/False로 작성한 코드에서 '우산' 유무에 따라 내구도 계산 코드를 짰지만, (pass는 받음)

아래 블로그의 코드가 더 직관적이라 작성해보고 첨부한다.

 

---

 

https://jisunshine.tistory.com/183 &rarr → 깔끔히 풀이를 정리했다

 

 

 

[기존 코드]

# 풀이 시간 : 1시간 10분 + 1시간 30분
# 시간복잡도 : O(n^2)
# 공간복잡도 : O(n^2)
# 참고 아이디어 : https://jisunshine.tistory.com/183
    # visited를 boolean으로 정의하고 풀 시, 우산을 획득하고 지나가는 효율적인 경로를 고려하지 못하게 된다.

import sys
from collections import deque

input = sys.stdin.readline

# N : 정사각현 한 번, H : 현재 체력, D : 우산의 내구도
N, H, D = map(int, input().split())

# U : 우산, S : dkswjswleo, . : 빈칸
ary = [list(map(str, input().rstrip())) for _ in range(N)]

dx = [-1,0,0,1]
dy = [0,-1,1,0]

ulist = []
for i in range(N):
    for j in range(N):
        if ary[i][j] == 'S':
            sx = i
            sy = j

        elif ary[i][j] == 'E':
            ex = i
            ey = j

q = deque()
q.append((sx, sy, H, 0, 0)) # 시작 좌표 x/y, 체력, 이동 거리, 우산 사이 걷는 거리
visited = [[0] * N for _ in range(N)] # 해당 지점에서 남은 체력
visited[sx][sy] = H

umbrella = False
while len(q)>0:
    x, y, power, dis, interval = q.popleft()

    # end 지점 도착
    if x == ex and y == ey:
        print(dis)
        exit()

    # 우산 도착
    if ary[x][y] == 'U':
        if umbrella: # 이전에 우산이 있는 상태
            if interval < D: # 우산 내구도가 남아있는 상태에서, 새로운 우산을 썼을 때
                power = power - (D - interval) # 남은 내구도 빼주기
        power += D
        interval = 0
        umbrella = True

    # 현재 체력을 다 소비하면
    if power == 0:
        continue

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if 0 <= nx < N and 0 <= ny < N:
            if power > visited[nx][ny]: # 현재 목숨 + 우산의 내구도의 합이 더 큰 경우
                visited[nx][ny] = power
                q.append((nx, ny, power-1, dis+1, interval+1))

print(-1)

 

 

[개선된 코드]

# 풀이 시간 : 1시간 10분 + 1시간 30분
# 시간복잡도 : O(n^2)
# 공간복잡도 : O(n^2)
# 참고 아이디어 : https://jisunshine.tistory.com/183
    # visited를 boolean으로 정의하고 풀 시, 우산을 획득하고 지나가는 효율적인 경로를 고려하지 못하게 된다.
    # 우산 내구도를 직관적으로 짠 코드

import sys
from collections import deque

input = sys.stdin.readline

# N : 정사각현 한 번, H : 현재 체력, D : 우산의 내구도
N, H, D = map(int, input().split())

# U : 우산, S : 안전지대, . : 빈칸
ary = [list(map(str, input().rstrip())) for _ in range(N)]

dx = [-1,0,0,1]
dy = [0,-1,1,0]

ulist = []
for i in range(N):
    for j in range(N):
        if ary[i][j] == 'S':
            sx = i
            sy = j

        elif ary[i][j] == 'E':
            ex = i
            ey = j

q = deque()
q.append((sx, sy, H+1, 0, 0))
visited = [[0] * N for _ in range(N)] # 해당 지점에서 남은 체력
visited[sx][sy] = H

# "출발지도 비를 맞게 코드를 작성해서, 체력을 +1 해준다."
while len(q)>0:
    # 시작 좌표 x/y, 남은 체력, 이동 거리, 우산 내구도
    x, y, power, dis, umbrella = q.popleft()

    # end 지점 도착
    if x == ex and y == ey:
        print(dis)
        exit()

    # 우산 도착
    if ary[x][y] == 'U':
        umbrella = D  # 우산 내구도 초기화

    # 우산 내구도부터 차감, 없으면 체력이 닳는다.
    if umbrella != 0:
        umbrella -= 1
    else:
        power -= 1

    # 현재 체력을 다 소비하면
    if power == 0:
        continue

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if 0 <= nx < N and 0 <= ny < N:
            if power + umbrella > visited[nx][ny]: # 현재 목숨 + 우산의 내구도의 합이 더 큰 경우
                visited[nx][ny] = power + umbrella
                q.append((nx, ny, power, dis+1, umbrella))

print(-1)