[백준][코틀린][12886] 돌 그룹

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

12886번: 돌 그룹

문제 풀이

1. 입력으로 주어지는 세 수를 queue 에 저장하고 BFS 를 수행한다.

2. 세 개의 수 중 서로 같지 않은 두 개의 수를 선택하기 때문에 아래의 3가지 경우에 대해서 반복 탐색 한다.

- (A, B), (A, C), (B, C)

3. 나머지 하나의 수는 세 수의 합에서 2번에서 선택된 두 수의 합을 뺀 값이다.

4. 따라서 이미 수행했는 지 여부를 확인하는 visit 배열은 2번의 두 수를 index 로 하는 2차원 Boolean 배열을 선언한다.

이때 크기를 최대 1500 으로 선언한다. 아래와 같은 경우 값이 계속 커지게 되는데 A, B, C 의 합의 최대값까지 배열의 크기로 설정한다.

- (500 499 498) -> (1 998, 498) -> (1, 500, 996) -> (1, 1000, 496) -> (1, 504, 992) -> (1, 1008, 488) ...

코드

import java.io.*
import java.util.*

fun main(args: Array<String>) {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val (A, B, C) = br.readLine().split(" ").map { it.toInt() }
    println("${bfs(A, B, C)}")
}

private fun bfs(A: Int, B: Int, C: Int): Int {
    val queue = LinkedList<Triple<Int, Int, Int>>()
    queue.add(Triple(A, B, C))
    val visit = Array(1500) { BooleanArray(1500) { false } }

    while (queue.isNotEmpty()) {
        val (cA, cB, cC) = queue.pop()
        //println("current $cA, $cB, $cC")

        if (cA == cB && cB == cC) {
            return 1
        }

        val sum = cA + cB + cC
        // i = 0 -> A, B 선택
        // i = 1 -> A, C 선택
        // i = 2 -> B, C 선택
        for (i in 0..2) {
            var num1 = cA
            var num2 = cB
            when (i) {
                0 -> {
                    num1 = cA
                    num2 = cB
                }
                1 -> {
                    num1 = cA
                    num2 = cC
                }
                2 -> {
                    num1 = cB
                    num2 = cC
                }
            }

            if (num1 > num2) {
                val temp = num2
                num1 -= temp
                num2 += temp
            } else {
                val temp = num1
                num1 += temp
                num2 -= temp
            }

            if (visit[num1][num2]) continue

            //println("next $num1, $num2, $num3")
            visit[num1][num2] = true
            queue.add(Triple(num1, num2, sum - (num1 + num2)))
        }
    }

    return 0
}