백준 22944 죽음의 비 Kotlin (bfs)

문제 출처 : https://www.acmicpc.net/problem/22944

22944번: 죽음의 비

문제

가로, 세로 길이가 N인 정사각형 격자가 있다. 해당 격자에는 두 곳을 제외한 모든 곳에 체력을 1씩 감소시키는 죽음의 비가 내리고 있다. 죽음의 비가 안내리는 곳은 현재 있는 위치와 안전지대라는 곳이다. 현재 있는 위치에도 곧 비가 내릴 예정이라 빨리 이 죽음의 비를 뚫고 안전지대로 이동해야한다.

다행히도 격자에는 죽음의 비를 잠시 막아주는 우산이 K개 존재한다. 우산에는 내구도 D라는 개념이 존재한다. 우산에 비를 맞으면 내구도가 1씩 감소하고, 내구도가 0이 되는 순간 우산은 사라진다. 문제에서 주어지는 우산의 내구도는 모두 D로 동일하다.

격자에서 이동을 할 때 다음과 같이 순서로 진행된다.

1. 상하좌우로 이동한다. 만약 이동할 곳이 격자 밖이라면 이동할 수 없다. 
2. 이동한 곳이 안전지대라면 반복을 종료한다.
3. 이동한 곳에 우산이 있다면 우산을 든다. 만약, 이동할 때부터 우산을 가지고 있다면 가지고 있는 우산을 버리고 새로운 우산으로 바꾼다.
   버린 우산은 더 이상 사용할 수 없다.
4. 죽음의 비를 맞았을 때, 우산을 가지고 있다면 우산의 내구도가 1이 감소하고 만약 우산을 가지고 있지 않는다면 체력이 1 감소한다.
5. 만약 우산의 내구도가 0이 되면 들고 있는 우산이 사라진다.
6. 만약 체력이 0이 되면 죽는다...
7. 아직 체력이 남았다면 안전지대까지 위 과정을 반복한다.

현재 있는 위치에서 안전지대로 얼마나 빠르게 이동할 수 있는지 구해주자.

입력

첫 번째 줄에 정사각형 격자의 한변의 길이인 N와 현재 체력 H, 우산의 내구도 D가 공백으로 구분되어 주어진다.

다음 N개의 줄에는 정사각형 격자의 정보가 N개의 문자로 붙어서 주어진다. 이때 주어지는 문자는 우산은 "U", 현재 있는 위치 "S", 안전지대 "E", 빈 칸 "."만 존재한다. 현재 있는 위치 "S"와 안전지대 "E"는 반드시 1개 존재한다.

출력

안전지대로 이동할 때 최소 이동 횟수를 출력한다. 만약 안전지대로 이동하지 못하는 경우에는 -1을 출력한다.

제한

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

최상단 맨 왼쪽을 (0, 0)이라 하고 최하단 맨 오른쪽을 (3, 3)이라 하자.

안전지대로 이동하는 방법은 (0, 0)에서 출발하여 우산이 있는 (0, 3)에 가고 (3, 3)으로 이동할 수 있다.

이 방식으로 이동한다면 안전지대에 도착했을때 체력이 1이 남는다.

알고리즘 분류

• 브루트포스 알고리즘
• 백트래킹

풀이

몇 시간 동안 맞왜틀 시전하다가 이번에도 갓민상님의 도움을 받아 해결했다. 어 근데 문제 만든 사람도 갓민상님이다.

역시 고인물들은 친절해.

바쁜 날에는, 알고리즘 문제를 하나만 풀고 다른 일을 하려 하는데, 꼭 그 한 문제가 오래 걸린다.

 

우선, 최소 이동 횟수를 구하고, 우산은 가는 길에 있으면 먹고 아니면 마는 경우만 생각하여서,

처음엔 그냥 bfs를 돌렸다.

60퍼 정도에서 틀렸는데, 이유를 생각해 보니, 주어진 HP로 S->E를 최단 경로로 가지 못하고, 우산을 먹으러 가서 우산을 먹고 다시 E를 향하여 최단 경로를 찾아야 하는 경우가 있었다. 

hp는 작게 주어지고 우산의 내구도는 크게 주어지는 경우를 생각하면 쉽다.

 

그래서 전역 변수로 우산의 인덱스를 두고, 우산을 먹을 때마다 bfs의 각 큐에 현재 먹은 우산의 인덱스를 넣어줬다.

그리고 방문 처리는 visited[몇 번째 우산?][r][c]로 처리해 주었다.

즉, 우산을 먹으면, 다시 모든 노드를 방문할 수 있다는 것을 3차원 배열에 우산의 인덱스로 구현한 것이다.

여기까지 생각이 다다르긴 오래 걸리지 않았다.

하지만.... 몇 시간 동안 맞왜틀을 시전하다가 헬프 요청을 한 결과...

우산이 있는 U칸에서도 비가 온다는 것을 간과한 것이 문제였다!!!

우산을 먹을 때 주어진 우산 내구도에서 -1을 해줌으로써 바로 통과했다.

 

문제를 꼼꼼히 읽는 습관을 가지자. 진짜 중요하다.

 

백트래킹 풀이도 가능하다.

 

S->U1->U2->E

S->U3->E

S ->E

등, 우산이 있는 칸을 방문, 방문하지 않는 경우 등의 모든 경우에서, 맨핸튼 거리와 내구도+HP를 비교하여 E에 도착할 수 있는지 없는지, 도착할 수 있다면 그중 가장 작은 값을 출력하면 된다.

 

개인적으로 백트래킹은 U가 많을 경우 오래 걸릴 것 같기도 하고, BFS 풀이가 좀 더 직관적인 것 같다.

위에 작성한 백트래킹 풀이는 러프하게 적어서 그렇지, 더 좋은 풀이가 있을 수 있다.

코드

import java.util.*

// 4<=n <=500 격자 크기
// 0<=k <=10 우산 개수
// 1<= h <= 10000 체력
// 1<= d <= 5000 우산 내구도
data class Node(var r : Int, var c : Int, var hp : Int, var umb : Int, var umbIdx : Int, var dis : Int)

val dir = arrayOf(
    arrayOf(1,0),
    arrayOf(0,1),
    arrayOf(-1,0),
    arrayOf(0,-1)
)
var nUmbIdx = 0
fun bfs(n : Int, h : Int, d : Int, sr : Int, sc : Int, graph : Array<CharArray>, visited : Array<Array<BooleanArray>>): Int{

    val q : Queue<Node> = LinkedList<Node>()
    q.add(Node(sr,sc,h,0,0, 0))
    visited[0][sr][sc] = true

    while(q.isNotEmpty()){
        val cur = q.poll()

        for(i in 0 until 4){
            val nr = cur.r+dir[i][0]
            val nc = cur.c+dir[i][1]
            var nUmb = cur.umb
            var nHp = cur.hp
            if(nr !in 0 until n || nc !in 0 until n) continue
            if(visited[cur.umbIdx][nr][nc]) continue
            //안전 지대 도착
            if(graph[nr][nc]=='E'){
                return cur.dis+1
            }
            //일반 땅
            else if(graph[nr][nc]=='.'){
                //우산 내구도 남아있으면 hp 대신 내구도 감소
                if (nUmb > 0) {
                    nUmb--
                }
                //우산이 없으면 hp 감소
                else {
                    nHp--
                }
            }
            //우산 찾으면 우산 내구도 리셋
            else{
                nUmb=d-1
                cur.umbIdx=++nUmbIdx
                graph[nr][nc]='.'
            }
            //hp 0이면 전진 불가
            if(nHp==0) continue
            visited[cur.umbIdx][nr][nc]=true
            q.add(Node(nr,nc,nHp,nUmb,cur.umbIdx,cur.dis+1))
        }
    }
    return -1
}

fun main() = with(System.out.bufferedWriter()){
    val br = System.`in`.bufferedReader()
    val (n,h,d) = br.readLine().split(' ').map{it.toInt()}
    var umbCnt=0
    var sr =0
    var sc =0
    val graph = Array(n){r->
        val sen = br.readLine()
        CharArray(n){c->
            var ch =sen[c]
           if(sen[c]=='S'){
               sr = r
               sc = c
               ch = '.'
           }
            else if(sen[c]=='U'){
                umbCnt++
           }
            ch
        }
    }

    write("${bfs(n,h,d,sr,sc,graph,Array(umbCnt+1){Array(n){BooleanArray(n)}})}")

    close()
}