백준 6987 월드컵 Kotlin (백트래킹) 2022-06-15 코드2 추가

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

6987번: 월드컵

문제

월드컵 조별 최종 예선에서는 6개국으로 구성된 각 조별로 동일한 조에 소속된 국가들과 한 번씩, 각 국가별로 총 5번의 경기를 치른다. 조별리그가 끝난 후, 기자가 보내온 각 나라의 승, 무승부, 패의 수가 가능한 결과인지를 판별하려고 한다. 다음은 가능한 결과와 가능하지 않은 결과의 예이다.

네 가지의 결과가 주어질 때 각각의 결과에 대하여 가능하면 1, 불가능하면 0을 출력하는 프로그램을 작성하시오.

입력

첫째 줄부터 넷째 줄까지 각 줄마다 6개국의 결과가 나라별로 승, 무승부, 패의 순서로 빈칸을 하나 사이에 두고 18개의 숫자로 주어진다. 승, 무, 패의 수는 6보다 작거나 같은 자연수 또는 0이다.

출력

입력에서 주어진 네 가지 결과에 대하여 가능한 결과는 1, 불가능한 결과는 0을 빈칸을 하나 사이에 두고 출력한다.

알고리즘 분류

• 브루트포스 알고리즘
• 백트래킹

풀이

백트래킹 문제이다.

처음엔 그냥 6팀의 승,무,패 모든 경우를 고르는 방식으로 dfs를 진행했으나 메모리 초과가 떴다.

이후 풀이를 보고 얻은 해결책은 다음과 같다.

우선 전체 경기의 가짓수는

A : BCDEF

B : CDEF

C : DEF

D : EF

E : F

F : 

와 같다.

이 15가지의 경기 가짓수에 team1이 이긴 경우, team1이 진 경우, 비긴 경우, 이 세 가지 경우를 골라주면서 탐색을 진행하면 된다.

따라서 먼저 15가지의 경기 가짓수를 배열로 저장해 놓고, 총 15경기를 dfs로 승,무,패를 정해 각 나라별 전적을 구한 후 input값과 비교한다.

이러한 방식으로 제출한 코드는

코틀린 기준 700ms 대 이다.

여기서 살짝 생각을 바꿔, 가능한 전적셋을 구하고 거기에 Input값이 해당되는지 찾는 게 아니라, 애초에 input값으로 dfs를 돌려 15번의 경기에 모두 승,무,패를 정할 수 있다면 해당 input은 유효한 값이 된다!

    //win
    input[t1][0]--
    input[t2][2]--
    if(input[t1][0]>=0 && input[t2][2] >=0) {
        backTracking(game + 1)
    }
    input[t1][0]++
    input[t2][2]++

예를 들어 위 코드처럼, 만약 input값에서 팀1(A,B,C,D,E 중 한 나라)가 이겼다면 input에서 해당 나라의 이긴 카운트를 하나 빼 준다.

만약 이긴 카운트가 0인데 이겼다고 하면 -1이 되므로, 실제 이 나라가 이긴 횟수보다 더 많이 이겼다고 하는 것이므로 가지치기에 걸린다.

따라서 뎁스가 15까지 무사히 간다면 이는 유효한 값으로 답이 된다.

메모리와 시간이 확 주는 것을 알 수 있다.

 

추가로 예제를 보면 알 수 있듯이 정답이 될수 없는 결과에 대해 직관적으로 확인할 수 있는 경우가 있다.

1. 승,패의 총합이 다른 경우

2. 비긴 팀이 한 팀밖에 없는 경우(혼자 비길 순 없잖아~) 

3. 승,무,패의 총합이 30이 아닌 경우

위 세가지 경우는 백트래킹을 돌리기 전 미리 걸러주었다.

 

코드1

import java.util.*
val br = System.`in`.bufferedReader()

val team1 = IntArray(15)
val team2 = IntArray(15)
var input = Array(6) { IntArray(3) }
var canMatch = 0
fun backTracking(game: Int) {

    if (canMatch == 1) return

    //end
    if (game == 15) {
        canMatch = 1
        return
    }

    val t1 = team1[game]
    val t2 = team2[game]

    //win
    input[t1][0]--
    input[t2][2]--
    if(input[t1][0]>=0 && input[t2][2] >=0) {
        backTracking(game + 1)
    }
    input[t1][0]++
    input[t2][2]++
    //draw
    input[t1][1]--
    input[t2][1]--
    if(input[t1][1]>=0 && input[t2][1] >=0) {
        backTracking(game + 1)
    }
    input[t1][1]++
    input[t2][1]++
    //lose
    input[t1][2]--
    input[t2][0]--
    if(input[t1][2]>=0 && input[t2][0] >=0) {
        backTracking(game + 1)
    }
    input[t1][2]++
    input[t2][0]++

}

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

    //preset
    var cnt = 0
    for (i in 0 until 6) {
        for (j in i + 1 until 6) {
            team1[cnt] = i
            team2[cnt] = j
            cnt++
        }
    }
    //input
    for (i in 0 until 4) {
        val tk = StringTokenizer(br.readLine())
        val info = IntArray(3)
        var drawCnt=0
        for (i in 0 until 6) {
            for (j in 0 until 3) {
                input[i][j] = tk.nextToken().toInt()
                info[j] +=input[i][j]
            }
            if(input[i][1]>0) drawCnt++
        }
        if (info[0] != info[2] || drawCnt == 1 || info[0] + info[1] + info[2] != 30) {
            write("0 ")
            continue
        }
        canMatch = 0
        //solve
        backTracking(0)
        //output
        write("$canMatch ")
    }
    close()
}

코드2 (2022-06-15, 풀이 동일) 

import java.util.*
val br = System.`in`.bufferedReader()
val matches = ArrayList<Pair<Int,Int>>()

val score = Array(6){IntArray(3)}
var answer = 0
fun dfs(idx: Int){
    if(idx== matches.size){
        answer= 1
        return
    }
    if(answer == 1) return
    val (a,b) = matches[idx]
    //승
    if(score[a][0]-1 >= 0 && score[b][2]-1 >= 0){
        score[a][0]--
        score[b][2]--
        dfs(idx+1)
        score[a][0]++
        score[b][2]++
    }
    //무
    if(score[a][1]-1 >= 0 && score[b][1]-1 >= 0 ){
        score[a][1]--
        score[b][1]--
        dfs(idx+1)
        score[a][1]++
        score[b][1]++
    }

    //패
    if(score[a][2]-1 >= 0 && score[b][0]-1 >= 0){
        score[a][2]--
        score[b][0]--
        dfs(idx+1)
        score[a][2]++
        score[b][0]++
    }
}

fun main() = with(System.out.bufferedWriter()){
    for(i in 0 until 5){
        for(j in i+1 until 6){
            matches.add(Pair(i,j))
        }
    }
    repeat(4) {
        //preset
        answer = 0
        //input
        var sum = 0
        StringTokenizer(br.readLine()).apply {
            var r = 0
            var c = 0
            while(hasMoreTokens()) {
                score[r++/3][c++%3] = nextToken().toInt().also{ sum+= it}
            }
        }
        //solve
        if(sum ==30)
            dfs(0)
        write("$answer ")
    }
    close()
}