[백준][Kotlin]2251번 물통

해당 문제는 진행 할 수 있는 경우는 총 6가지가 있음을 알고, 그래프를 그리는 시점으로 보면 작성 할 수 있는 문제였습니다. 

A,B,C 물통으로 진행 할 수 있는 방법은 AB,AC,BA,BC,CA,CB으로 6개 입니다. 그렇다면 이것을 배열로 만들었을 경우

주는 통(0,0,1,1,2,2) 받는 통 (1,2,0,2,0,1) 이며,  이는 반복문을 통하여 추후 모든 진행 방향을 간단히 확인 할 수 있습니다.

 

그리고 A가 비어 있을 때 세 번째 물통의 용량을 구하기 위하여 세번째 물통의 최대 용량+1의 사이즈를 가진 Boolean 배열을 생성하며(해당 배열은 A가 0일 때 C의 값을 저장하기 위한 용도), A,B의 값은 최대 0~200 이 될 수 있으므로 201의 사이즈를 가진 201사이즈의 Boolean 이차원 배열을 생성합니다.(2개만을 한 이유는 물의 총량은 정해져 있어 A,B를 알면 C를 구할 수 있기 때문입니다.) 해당 배열을 생성한 이유는 A,B의 값으로 해당 용량일 때 확인 유무 체크를 하기 위함입니다.

 

위 와 같은 개념과 BFS를 이용하여 코드를 작성하면 해당 문제를 작성 할 수 있습니다.

 

하기는 제출한 코드와 제출 결과 입니다.

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

var start = intArrayOf(0,0,1,1,2,2)
var end = intArrayOf(1,2,0,2,0,1)
lateinit var arr: IntArray // 물의 양 저장 목적
var answer = BooleanArray(201) // 기본 false 결과값 저장 배열(C의 양에 해당하는 인덱스 true 처리)
var visit = Array(201,{BooleanArray(201)}) // a와b의 물의 양에 따른 방문체크

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    var bw = BufferedWriter(OutputStreamWriter(System.out))
    var st = StringTokenizer(br.readLine())
    arr = intArrayOf(st.nextToken().toInt(),st.nextToken().toInt(),st.nextToken().toInt())

    bfs()

    for(i in 0 .. answer.size-1){
        if(answer[i]) bw.append("$i ")
    }

    bw.flush()
    bw.close()

}

fun bfs(){
    visit[0][0] = true
    answer[arr[2]] = true

    var dq = ArrayDeque<Info>() // a와b의 물의 양 저장
    dq.add(Info(0,0))

    while(!dq.isEmpty()){
        val now = dq.poll()
        val a = now.A
        val b = now.B
        val c = arr[2]-a-b

        for(i in 0 .. 5){
            var temp = intArrayOf(a,b,c)
            temp[end[i]] += temp[start[i]]
            temp[start[i]] = 0
            if(temp[end[i]] > arr[end[i]]){ // 물이 넘쳤을 경우
                temp[start[i]] = temp[end[i]] - arr[end[i]]
                temp[end[i]] = arr[end[i]]
            }
            if(!visit[temp[0]][temp[1]]){
                visit[temp[0]][temp[1]] = true
                dq.add(Info(temp[0],temp[1]))
                if(temp[0].equals(0)){
                    answer[temp[2]] = true
                }
            }
        }

    }

}

data class Info(
    val A: Int,
    val B: Int
)