백준 2251 물통 Kotlin (bfs)

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

2251번: 물통

문제

각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부을 수 있는데, 이때에는 한 물통이 비거나, 다른 한 물통이 가득 찰 때까지 물을 부을 수 있다. 이 과정에서 손실되는 물은 없다고 가정한다.

이와 같은 과정을 거치다보면 세 번째 물통(용량이 C인)에 담겨있는 물의 양이 변할 수도 있다. 첫 번째 물통(용량이 A인)이 비어 있을 때, 세 번째 물통(용량이 C인)에 담겨있을 수 있는 물의 양을 모두 구해내는 프로그램을 작성하시오.

입력

첫째 줄에 세 정수 A, B, C가 주어진다.

출력

첫째 줄에 공백으로 구분하여 답을 출력한다. 각 용량은 오름차순으로 정렬한다.

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 깊이 우선 탐색

풀이

bfs 혹은 dfs로 풀 수 있는 문제다.

a,b,c의 상태에 따른 방문 체크를 위해 visited[][][] 3차원 배열을 사용하고,

a에서 b,c로 가는 경우

b에서 a,c로 가는 경우

c에서 a,b로 가는 경우

위의 경우들이 탐색 경로이다.(큐에 삽입한다.)

탐색 중 현재 a가 0인 경우(A 물통이 빈 경우)는 C 물통의 현재 용량을 정답 리스트에 삽입하고, 최종적으로 이를 정렬하여 출력한다.

 

물통의 용량을 A,B,C라 하고, 각각 들어있는 용량을 a,b,c라고 할 때,

이동 가능한 조건은 A에서 B로 간다고 하면,

a+b가 B의 용량보다 클 땐 A에 a+b-B만큼 남고 B엔 B만큼 꽉 차게 된다.

a+b가 B의 용량보다 작거나 같을 땐, A엔 0이 남고, B엔 a+b만큼 차게 된다.

코드

import java.util.*
val br = System.`in`.bufferedReader()
fun getIntList() = br.readLine().split(' ').map { it.toInt() }
fun getInt() = br.readLine().toInt()

lateinit var visited: Array<Array<BooleanArray>>
val answer = ArrayList<Int>()

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

fun bfs(A: Int, B: Int, C: Int) {
    val q: Queue<State> = LinkedList()
    q.add(State(0, 0, C))

    while (q.isNotEmpty()) {
        val (a, b, c) = q.poll()
        if (visited[a][b][c]) continue
        visited[a][b][c] = true
        if (a == 0) {
            answer.add(c)
        }
        //a->b
        if (a + b > B) q.add(State(a + b - B, B, c))
        else q.add(State(0, a + b, c))
        //a->c
        if (a + c > C) q.add(State(a + c - C, b, C))
        else q.add(State(0, b, a + c))
        //b->a
        if (a + b > A) q.add(State(A, a + b - A, c))
        else q.add(State(a + b, 0, c))
        //b->c
        if (b + c > C) q.add(State(a, b + c - C, C))
        else q.add(State(a, 0, b + c))
        //c->a
        if (a + c > A) q.add(State(A, b, a + c - A))
        else q.add(State(a + c, b, 0))
        //c->b
        if (b + c > B) q.add(State(a, B, b + c - B))
        else q.add(State(a, b + c, 0))
    }
}

fun main() = with(System.out.bufferedWriter()) {

    //input
    val (A, B, C) = getIntList()
    visited = Array(201) { Array(201) { BooleanArray(201) } }
    //solve
    bfs(A, B, C)
    //output
    write(answer.sorted().joinToString(" "))
    close()
}