[Swift] 백준 6987: 월드컵

6987번: 월드컵

문제

월드컵 최종 예선에서는 6개국으로 구성

각 국가별로 한 번씩 총 5번의 경기

각 나라의 승, 무승부, 패를 보여주는 결과지

네 가지의 결과에서 가능한 결과라면 1, 불가능이라면 0으로 출력

제한사항

• 네 가지의 결과지
• 6개국의 결과로 승, 무승부, 패의 순서로 빈칸을 포함하여 18개 숫자로 구성

 

풀이

이게 어렵나? 승과 패가 같고 무승부를 대응해서 풀면 되지

안되더라... 문제 유형이 백트래킹에 맞춰 고민하기 시작했다.

 

일단 월드컵의 경기는 총 15번을 진행한다.

A-B, A-C ... E-F 로 경기는 조합(Combination)으로 𝗻C𝗿 이다.

 

조합을 통해서 모든 경기를 기록해보자

visit의 true 갯수가 r의 숫자와 동일하면 combination 이라는 배열에 값을 넣어준다.

func combination(n: Int, r: Int) -> [[Int]] {
    var combination = [[Int]]()
    var visit = Array(repeating: false, count: n)

    func combination_DFS(_ index: Int, _ count: Int) {
        guard count < r else {
            combination.append(visit.enumerated().filter { $0.element }.map { $0.offset })
            return
        }

        for i in index..<n {
            visit[i] = true
            combination_DFS(i+1, count + 1)
            visit[i] = false
        }
    }

    combination_DFS(0, 0)
    return combination
}

 

문제에서는 6개국에서 국가 2개를 뽑아서 경기를 치루기에 n = 6, r = 2를 매개변수로 넣어주면 combination 값을 얻을 수 있다.

이제 모든 국가가 경기를 치루는 경우의 수를 얻었다.

 

각 게임에서는 3개의 결과가 있다.

• 승 / 패
• 무 / 무
• 패 / 승

경기를 치룰 때, 3가지 중 해당하는 결과는 백트래킹으로 하나씩 확인을 해본다.

결과지에 국가 A는 4승 1무 0패, 국가 B는 3승 1무 1패로 기록되었다고 가정하자.

여기에서 가능한 결과는 승/패, 무/무만 가능하다. 국가 A에서는 0패이기에 국가 B의 경기에서 질 수 없다.

 

이렇게 모든 가능한 결과에 대해서 백트래킹을 이용해서 모든 15가지의 경기를 확인하면 된다.

각 경기에서는 가능하다면 스코어를 차감하여 최종적으로 모든 스코어가 0인 경우가 단 하나라도 있으면 가능한 결과가 된다는 말이다.

이제 코드를 통해서 해결해보자.

 

코드

import Foundation

func combination(n: Int, r: Int) -> [[Int]] {
    var combination = [[Int]]()
    var visit = Array(repeating: false, count: n)

    func combination_DFS(_ index: Int, _ count: Int) {
        guard count < r else {
            combination.append(visit.enumerated().filter { $0.element }.map { $0.offset })
            return
        }

        for i in index..<n {
            visit[i] = true
            combination_DFS(i+1, count + 1)
            visit[i] = false
        }
    }

    combination_DFS(0, 0)
    return combination
}

// 월드컵에서 진행된 모든 경기
let game = combination(n: 6, r: 2)

var answer = [Int]()
var ret = 0
var board = [[Int]]()

func game_DFS(_ count: Int) {
    // 모든 경기를 치뤘다면
    guard count < game.count else {
        // 이미 ret이 1이라면 통과
        for country in board where ret == 0 {
            // score가 0보다 크면 불가능한 결과
            for score in country where score > 0 {
                return
            }
        }
        ret = 1
        return
    }

	// 겨루는 국가
    let g1 = game[count][0]
    let g2 = game[count][1]

    // 승/패, 무/무, 패/승
    for (x, y) in [(0, 2), (1, 1), (2, 0)] {
        if board[g1][x] > 0, board[g2][y] > 0 {
            board[g1][x] -= 1
            board[g2][y] -= 1
            game_DFS(count+1)
            board[g1][x] += 1
            board[g2][y] += 1
        }
    }
}

(1...4).forEach { _ in
    let input = readLine()!.split(separator: " ").map { Int($0)! }
    board = (0...5).map { Array(input[$0*3..<($0+1)*3]) }
    ret = 0
    game_DFS(0)
    answer.append(ret)
}

answer.forEach { print($0, terminator: " ") }