[Kotlin] 백준 2412번 - 암벽 등반

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

2412번: 암벽 등반

유형

HashSet + BFS (이분탐색을 사용해서 그래프를 따로 만들어서 풀 수도 있다고 한다.)

풀이

완전 탐색을 가장 먼저 떠올릴 수 있다, 시작점에서 모든 경우의 수를 다 가보는 것. 최소 횟수로 T에 도달하길 원하기 때문에 다른 경우의 수에서 이미 가본 곳을 다시 가보는 건 손해 -> 시간 초과가 난다. 따라서 이미 가본 곳은 다시 가지 않도록 한다. 이렇게 완전한 BFS 풀이가 됐다.

그래프와 visited는 어떻게?

그래프는 HashSet으로 나타낼 수 있다. x,y좌표로 Pair나 문자열을 구성해서 Set에 전부 저장한다. 그러면 현재 위치에서 -2 ~ +2를 한 새로운 좌표가 그래프에 포함되는지 바로 확인할 수 있다. 따라서, visited도 HashSet으로 나타낼 수 있다.

for (dx in -2..2) {
    val nextX = x + dx
    
    for (dy in -2..2) {
        val nextY = y + dy
        val coord = Pair(nextX, nextY)
        // holes: 그래프(홈)
        if (holes.contains(coord) && visited.contains(coord).not()) {
            visited.add(coord)
            q.offer(Triple(nextX, nextY, count + 1))
        }
    }
}

BFS도중 y좌표가 T인 걸 만나면 그동안 움직인 횟수를 출력, 그렇지 못했다면 마지막에 -1을 출력해준다..!

코드

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

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val (n, targetY) = readLine().split(" ").map(String::toInt)
    val holes = HashSet<Pair<Int, Int>>()
    val visited = HashSet<Pair<Int, Int>>()
    repeat(n) {
        val st = StringTokenizer(readLine())
        holes.add(Pair(st.nextToken().toInt(), st.nextToken().toInt()))
    }

    val q: Queue<Triple<Int, Int, Int>> = LinkedList()
    q.offer(Triple(0, 0, 0))

    while(q.isNotEmpty()) {
        val (x, y, count) = q.poll()

        if (y == targetY) {
            print(count)
            return
        }

        for (dx in -2..2) {
            val nextX = x + dx
            for (dy in -2..2) {
                val nextY = y + dy
                val coord = Pair(nextX, nextY)
                if (holes.contains(coord) && visited.contains(coord).not()) {
                    visited.add(coord)
                    q.offer(Triple(nextX, nextY, count + 1))
                }
            }
        }
    }

    print(-1)
}