[백준 2251번] [Kotlin] 물통

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

2251번: 물통

 

난이도 : 골드 5
태그 : 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색

 

 

설명

꽤 유명한 물통 문제 입니다.

해당 문제에서는 모든 경우의 수를 탐색해야 하므로, DFS, BFS 중 어느것을 사용해도 무방하나

 

 

 

소스코드

import java.lang.StringBuilder
import java.util.LinkedList
import java.util.Queue

data class Bottle(val a: Int, val b: Int, val c: Int)

fun main() = with(System.`in`.bufferedReader()) {
    val capacity = readLine().split(" ").map { it.toInt() }.toTypedArray()

    // a, b는 빔, c는 가득 참
    val visited = Array(capacity[0] + 1) { Array(capacity[1] + 1) { Array(capacity[2] + 1) { false } } }
    val answer = Array(capacity[2] + 1) { false }

    val q = LinkedList<Bottle>() as Queue<Bottle>
    q.offer(Bottle(0, 0, capacity[2]))

    while (q.isNotEmpty()) {
        val target = q.poll()
        val a = target.a
        val b = target.b
        val c = target.c

        if (visited[a][b][c]) continue
        visited[a][b][c] = true

        if (a == 0) {
            answer[c] = true
        }

        // a -> b
        if (a + b > capacity[1]) {
            q.offer(Bottle(a + b - capacity[1], capacity[1], c))
        } else {
            q.offer(Bottle(0, a + b, c))
        }

        // a -> c
        if (a + c > capacity[2]) {
            q.offer(Bottle(a + c - capacity[2], b, capacity[2]))
        } else {
            q.offer(Bottle(0, b, a + c))
        }

        // b -> a
        if (a + b > capacity[0]) {
            q.offer(Bottle(capacity[0], a + b - capacity[0], c))
        } else {
            q.offer(Bottle(a + b, 0, c))
        }

        // b -> c
        if (b + c > capacity[2]) {
            q.offer(Bottle(a, b + c - capacity[2], capacity[2]))
        } else {
            q.offer(Bottle(a, 0, b + c))
        }

        // c -> a
        if (a + c > capacity[0]) {
            q.offer(Bottle(capacity[0], b, a + c - capacity[0]))
        } else {
            q.offer(Bottle(a + c, b, 0))
        }

        // c -> b
        if (b + c > capacity[1]) {
            q.offer(Bottle(a, capacity[1], b + c - capacity[1]))
        } else {
            q.offer(Bottle(a, b + c, 0))
        }
    }

    val sb = StringBuilder()
    for (i in 0..capacity[2]) {
        if (answer[i]) {
            sb.append("$i ")
        }
    }

    println(sb.toString())
}

 

a, b, c의 물이 얼만큼 담겨있는지 각 경우를 visited로 확인하고, 이미 방문했다면 다음 케이스로 넘어갑니다.

 

answer는 c 물통의 상태를 확인하는 배열로,

a 물통이 비어있을 때, 가능한 c 물통의 용량을 구하는 문제이므로,

a == 0 일때 answer[c]를 true로 변경합니다.

 

 

후기

가능한 모든 C의 상태를 출력하는 문제인줄 알고, 한참 고민했는데,

A가 0 일때 가능한 C의 상태를 출력하는 문제였습니다.

항상 코테를 풀기 전 문제를 꼼꼼히 읽어보는 습관을 가져야 할 것 같습니다. ㅠㅠ