[백준 1445] - 일요일 아침의 데이트(Kotlin)[골드2]

문제

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

1445번: 일요일 아침의 데이트

 

문제 풀이

나는 해당 문제를 전형적인 bfs 문제라고 생각한다. 하지만 bfs 문제에서도 조금 더 진화한 문제이다.

우선 문제 초기에는 DP를 사용해서 주변에 존재하는 쓰레기를 저장해서 방문 처리를 하려고 했지만,

결과적으로 도착지점에 도착한 경우에 최적의 도착을 해야하기 때문에, 도착한 시점에 우리는 가장 적은 쓰레기를 마주치고 밟아야 한다.

그렇기 때문에 DP를 사용하기에는 최적의 도착을 계산할 수 있지만, 최초의 도착이 최적의 도착이라고 장담할 수는 없다.

그렇다면 우리는  다음 방문을 준비할 때 항상 해당 방문이 최적이어야 한다.

따라서 해당 문제는 우선순위 큐를 사용해서 푸는 것이 맞다고 생각한다.

 

그렇다면 우선순위 큐를 사용한다면 어떠한 기준으로 정렬을 해야 할까?

문제에서는 가장 적은 쓰레기를 "밟고", 가장 적은 쓰레기 주변을 지나가야 한다.

따라서 1차적으로 쓰레기를 가장 적게 밟는 것을 기준으로 정렬하고, 그다음으로는 이제 가장 적은 쓰레기 주변을 지나는 것을 기준으로 정렬을 하면 쉽게 풀 수 있을 것이다.

해당 문제는 왜 PQ를 사용해야 하느냐에 대한 접근이 어려운 문제고, 푸는 것 자체는 어렵지 않다고 생각한다.

 

나 같은 경우도 문제를 잘못 읽어서 문제를 잘못해석했었다.

 

1. 모든 방문에 대해서 주변에 쓰레기가 있는지에 대해서 검사했었다.

해당 접근 방법은 잘못된 접근 방법이다.

우선 S와 F 주변에는 쓰레기가 있든지 말든지 계산하지 않는다.

그리고 방문한 칸이 쓰레기가 있다면 주변에 쓰레기가 있는 것을 신경 쓰지 않는다.

즉 빈칸인 경우에만 주변에 쓰레기가 있는지 검사하는 것이다.

 

2. 주변에 쓰레기를 검사하는 과정에서 주변 모든 쓰레기의 숫자를 더했다.

 

정말 잘못된 접근 방법이었다.

이제 이동하는 칸이 쓰레기와 인접한 지, 안 한 지를 계산하는 것이라서, 쓰레기가 있다면 +1, 쓰레기가 없다면 +0이지만,

나는 4방향에서 쓰레기가 있는 개수를 더해서 더해줬고, 당연하게도 인접한 쓰레기의 개수가 너무 많이 나왔었다.

우리가 구하는 것은 쓰레기의 개수가 아니고, 인접한 쓰레기를 지나가는 칸의 수이기 때문에 쓰레기가 있다는 여부만 검사하면 된다.

 

위에 1,2번만 신경 써서 풀면 다른 bfs 문제와 다를 문제가 없다.

 

🙏전체코드와 주석을 읽어주시면 이해가 빠를 겁니다!!

전체 코드

package Graph.`1445_일요일_아침의_데이트`

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

class `1445` {
    private val br = BufferedReader(InputStreamReader(System.`in`))
    private var n = 0
    private var m = 0
    lateinit var graph: Array<Array<Char>>
    lateinit var visit: Array<Array<Boolean>>
    val x = arrayOf(1, -1, 0, 0)
    val y = arrayOf(0, 0, -1, 1)
    data class Walk(var x: Int = 0, var y: Int = 0, var nearG: Int = 0, var meetG: Int = 0){
        override fun toString(): String {
            return "$x $y $nearG $meetG"
        }
    }
    val pq = PriorityQueue<Walk>(compareBy({+it.meetG}, {+it.nearG}) ) //쓰레기를 밟은 갯수 > 쓰레기 주변을 지나간 개수
    private lateinit var s : Pair<Int,Int>
    private lateinit var f : Pair<Int,Int>

    init {
        input()
        bfs()
    }

    fun input() {
        br.readLine().split(" ").forEachIndexed { index, s ->
            when (index) {
                0 -> n = s.toInt()
                1 -> m = s.toInt()
            }
        }
        graph = Array(n) { Array(m) { ' ' } }
        visit = Array(n) { Array(m) { false } }
        for (i in 0 until n) {
            val line = br.readLine().toCharArray()
            for (j in 0 until m) {
                graph[i][j] = line[j]
                if (line[j] == 'S')
                    s = Pair(i,j)
                else if (line[j] == 'F')
                    f = Pair(i,j)
            }
        }
    }

    private fun bfs() {
        pq.add(Walk(s.first,s.second,0,0))
        visit[s.first][s.second]=true
        while (!pq.isEmpty()) {
            val now = pq.poll()
            for (dir in 0 until 4) {
                var near = now.nearG
                var goal = now.meetG
                val moveX = now.x + x[dir]
                val moveY = now.y + y[dir]
                if (moveX !in graph.indices || moveY !in graph[0].indices)
                    continue
                if(moveX==f.first && moveY ==f.second) { //도착지점일 경우 만난 쓰레기와 인접한 쓰레기를 출력
                    print("$goal $near")
                    return
                }
                if(visit[moveX][moveY]) //방문처리
                    continue
                if(graph[moveX][moveY]=='.') //빈칸이라면
                    near += checkGarbage(moveX,moveY)
                if (graph[moveX][moveY] == 'g') goal++ //쓰레기라면
                pq.add(Walk(moveX,moveY,near,goal))
                visit[moveX][moveY]=true
            }
        }
    }
    private fun checkGarbage(row : Int, col : Int) : Int{ // 주변 쓰레기의 여부를 검사하는 함수.
        for(dir in 0 until 4){
            val moveX = row+x[dir]
            val moveY = col+y[dir]
            if (moveX !in graph.indices || moveY !in graph[0].indices)
                continue
            if(graph[moveX][moveY]=='g') // 있다면 1을 리턴
                return 1
        }
        return 0 //없다면 0을 리턴
    }
}

fun main() {
    val solution = `1445`()
}