글 읽기 - 골드5 백트래킹 한번만 도와주십쇼

inqbator 2년 전 0

질문글 다 확인했습니다.

각 국가의 전적은 overalls

A 3승 0무 2패

B 4승 2무 1패

{{3,0,2}, {4,2,1}} 이런 식으로 2차원 배열로 처리하였습니다.

로직은 일단, 첫번째 국가를 기준으로 기준 국가의 전적이 0이 될 때까지 만든 후에, 다음 국가를 확인하는 방식입니다. 백트래킹이라고 나름 짰는데

하루종일 잡았는데 도저히 모르겠습니다.

import java.io.BufferedReader
import java.io.InputStreamReader


// 각 국가별로 승, 무,패를 담을 2차원 배열
val overalls = Array(6) {IntArray(3)}
val totalOverall = IntArray(3)
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val sb = StringBuilder()
    // 입력
    for (i in 0..3) {
        val input = readLine().split(" ").map { it.toInt() }.toIntArray()
        // 만약 전적의 총합이 5보다 크면, 불가능한 게임이므로 다음 입력 받음
        if (!makeArray(input)) {
            sb.append("0").append(" ")
            continue
        }

        // 가능한 게임이면 1 붙이고 아니면 0 붙이기
        if (getIsPossible(0,0)) {
            sb.append("1")
        } else {
            sb.append("0")
        }
        sb.append(" ")
    }
    println(sb)
}

// 각 국가의 총 게임수가 5를 넘으면, 불가능한 게임으로 false 리턴
fun makeArray(input: IntArray): Boolean {
    for(it in 0 ..5) {
        var sum = input[it*3]
        sum += input[it*3+1]
        sum += input[it*3+2]
        if (sum != 5) {
            return false
        }

        overalls[it][0] = input[it*3]
        overalls[it][1] = input[it*3+1]
        overalls[it][2] = input[it*3+2]
        totalOverall[0] += input[it*3]
        totalOverall[1] += input[it*3+1]
        totalOverall[2] += input[it*3+2]
    }

    return true
}

fun getIsPossible(idxOfPivotCountry: Int, idxOfOverall: Int): Boolean {
    // 전적(승,무,패)이 0이면 계산할 필요가 없는 전적임.
    if (overalls[idxOfPivotCountry][idxOfOverall] == 0) {
        // 승, 무, 패를 전부 계산했으면, 다음 나라를 기준으로 검색
        if (idxOfOverall+1 ==  3) {
            // 다음 나라가 없으면 현재 완성 된 전적이 모두 0인지 확인
            if (idxOfPivotCountry+1 >= 6) {
                // 다음 나라가 없으면 현재 완성 된 전적이 모두 0인지 확인
                for (row in overalls.indices) {
                    for (column in overalls[0].indices) {
                        // 0이 아닌 애가 있으면, 가능한 경기가 아님.
                        if (overalls[row][column] != 0) {
                            return false
                        }
                    }
                }

                // 모든 전적이 0이므로 가능한 경기 -> true를 반환
                return true
            } else {
                return getIsPossible(idxOfPivotCountry+1, 0)
            }
        } else {
            // 다음 전적을 비교함(승 -> 무, 무 -> 패)
            return getIsPossible(idxOfPivotCountry, idxOfOverall+1)
        }
    } else if (overalls[idxOfPivotCountry][idxOfOverall] > 0) {
        for (idxOfEnemyCountry in overalls.indices) {
            // 상대가 자기 자신이면 넘어감
            if (idxOfEnemyCountry == idxOfPivotCountry) {
                continue
            }

            // 백트래킹으로 모든 경우의 수 구하기
            // 승이면, 상대방은 패가
            // 패면, 상대방은 승이
            // 무승부면, 서로 무승부가 줄어듬
            when (idxOfOverall) {
                0 -> {
                    if (overalls[idxOfEnemyCountry][2] > 0) {
                        overalls[idxOfEnemyCountry][2]--
                        overalls[idxOfPivotCountry][0]--

                        if (getIsPossible(idxOfPivotCountry, idxOfOverall)) {
                            return true
                        }
                        overalls[idxOfEnemyCountry][2]++
                        overalls[idxOfPivotCountry][0]++
                    }
                }
                1 -> {
                    if (overalls[idxOfEnemyCountry][1] > 0) {
                        overalls[idxOfEnemyCountry][1]--
                        overalls[idxOfPivotCountry][1]--

                        if (getIsPossible(idxOfPivotCountry, idxOfOverall)) {
                            return true
                        }

                        overalls[idxOfEnemyCountry][1]++
                        overalls[idxOfPivotCountry][1]++
                    }
                }
                2 -> {
                    if (overalls[idxOfEnemyCountry][0] > 0) {
                        overalls[idxOfEnemyCountry][0]--
                        overalls[idxOfPivotCountry][2]--

                        if (getIsPossible(idxOfPivotCountry, idxOfOverall)) {
                            return true
                        }

                        overalls[idxOfEnemyCountry][0]++
                        overalls[idxOfPivotCountry][2]++
                    }
                }
            }
        }
    }

    return false
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

골드5 백트래킹 한번만 도와주십쇼

inqbator 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말