[백준 6987] 월드컵 (Swift)

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

Simulation + DFS

6개국이 서로 한번씩 경기한다고 했을 때, 경기결과를 각 나라마다 승,무,패 횟수로 정리한 표를 보고

가능한 결과인지 아닌지 판단하는 문제

 

접근방법

처음에 브루트포스, 백트래킹이라고 써있어서 접근하기 너무 어렵다가

나라별로 경기를 치르는 대진의 총 개수가 15개 라는 것을 보고

한 경기의 대진을 ( A , B ) 라고 했을 때 15개의 모든 경우를 배열로 저장했다. [(1,2),(1,3),....,(5,6)] 이런식으로

그리고 이제 한 경기를 하나의 노드라고 보고 dfs 탐색을 진행하면서

각 노드 마다 뻗어나가는 가지는 A>B, A=B, A<B 세가지가 있을 수 있다고 생각하고 모든 경우를 완전탐색하는 것

 

그러면 모든 경기의 모든 경우의 수를 고려해볼 수 있다.

N이 정해져있어서 가능한 것 같음

 

이때 예제 결과 하나 마다 dfs를 수행해줬는데,

저 표에서 1씩 빼가면서 모든 경기를 치르고 나면 저 결과 표가 모두 0으로 채워지고, 마지막 경기 (5,6) 까지 끝났다면

이 표는 가능한 결과가 되는 것이고, (1 반환)

만약 마지막 경기까지 도달하지 못하고 중간에 불가능한 결과라고 판정되거나, 마지막경기까지 치렀는데 표에 숫자가 남아있다면 역시 불가능한 결과 -> 0 반환

 

오답노트

세가지 모든 경우를 병렬적으로 볼 수 있게 해야되는데

저 if 문 앞에 else if 써놨었음;

 

소스코드

import Foundation

func solution() {
    
    var ab:[(Int, Int)] = []
    for a in 1...5 {
        for b in a+1...6 {
            ab.append((a,b))
        }
    }
    
    var result = 0
    var answers:[Int] = []

    func dfs(_ i:Int, _ scores:[[Int]]) {
        if i == 15 {
            // 종료
            if scores.allSatisfy({ row in row.allSatisfy { $0 == 0 }}) {
                result = 1
            } else {
                result = 0
            }
            return
        }
        
        var _scores = scores
        let a = ab[i].0
        let b = ab[i].1
        
        if scores[a][0] > 0 && scores[b][2] > 0 {
            // a > b
            _scores[a][0] -= 1
            _scores[b][2] -= 1
            dfs(i+1, _scores)
            _scores[a][0] += 1
            _scores[b][2] += 1
        }
        if scores[a][1] > 0 && scores[b][1] > 0 {
            // a = b
            _scores[a][1] -= 1
            _scores[b][1] -= 1
            dfs(i+1, _scores)
            _scores[a][1] += 1
            _scores[b][1] += 1
        }
        if scores[a][2] > 0 && scores[b][0] > 0 {
            // a < b
            _scores[a][2] -= 1
            _scores[b][0] -= 1
            dfs(i+1, _scores)
            _scores[a][2] += 1
            _scores[b][0] += 1
        }
        
        
    }
    
    
    for i in 0..<4 {
        result = 0
        var scores:[[Int]] = [[Int]](repeating: [], count: 7)
        
        let arr:[Int] = (readLine()?.split(separator: " ").map { Int($0)! })!
        for i in 0..<arr.count {
            scores[i/3+1].append(arr[i])
        }
        
        dfs(0, scores)
        answers.append(result)
    }
    
    print(answers.reduce("") { pre, new in
        return pre+"\(new) "
    })
    return
}

solution()