[JUNGOL] 1841. 월드컵 - DFS

[JUNGOL] 1841. 월드컵 - DFS

제출일 : 2019-10-01

문제 풀이 시간 : 1H 45M

난이도 : ★★★☆

Problem

link : http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1114&sca=50&stx=%EC%9B%94%EB%93%9C%EC%BB%B5

Input

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

Output

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

Example

input

5 0 0 3 0 2 2 0 3 0 0 5 4 0 1 1 0 4 
4 1 0 3 0 2 4 1 0 1 1 3 0 0 5 1 1 3 
5 0 0 4 0 1 2 2 1 2 0 3 1 0 4 0 0 5
5 0 0 3 1 1 2 1 2 2 0 3 0 0 5 1 0 4

output

1 1 0 0

Solution & Inpression

결과적으론 BFS를 이용하면 된다.

하지만 나는 단순하게 조건을 주어 해결하려 하였다. 하지만 계속 예외가 발생했고 생각하지 못한 조건들이 계속 발견되어 총 라인수가 150라인을 넘어가고있었다.

다시 생각을 하였다.

---

전체 경기는 총 15번 진행된다

A vs B C D E F
B vs C D E F
C vs D E F
D vs E F
E vs F

또한 각 경기는 3가지 경우가 존재한다

• Team1 승리 , Team2 패배
• Team1 비김 , Team2 비김
• Team1 패배 , Team2 승리

이때 시간복잡도는 O(3^15) 로 완전탐색을 진행할 수 있다.

---

따라서 완전탐색을 이용하여 문제를 해결하였다.

Code

언어 : JAVA

메모리 : 16 mb

실행시간 : 1009 ms

import java.util.Scanner;

public class Main {

    static int[] team1 = { 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 3, 3, 4 };
    static int[] team2 = { 1, 2, 3, 4, 5, 2, 3, 4, 5, 3, 4, 5, 4, 5, 5 };
    static int[][] matrix;
    static int[][] result;
    static int[] ans;

    static void dfs(int tc, int game) {
        if (game == 15) { // 모든 경기를 마치고
            if (ans[tc] != 1) { // 이전에 판별되지 않았다면
                // 판별시작
                for (int i = 0; i < 6; i++) {
                    for (int j = 0; j < 3; j++)
                        // 결과가 하나라도 같지 않다면
                        if (matrix[i][j] != result[i][j])
                            return;
                }

                // 경기결과가 일치한다면
                ans[tc] = 1; // 결과테이블에 저장
                return;

            } else
                return;
        }

        // ---------------------DFS--------------------- //
        // |승0|무1|패2|

        int t1 = team1[game];
        int t2 = team2[game];

       // t1 win, t2 lose
        result[t1][0]++;        result[t2][2]++;
        dfs(tc, game + 1);
        result[t1][0]--;        result[t2][2]--;

        // t1 draw, t2 draw
        result[t1][1]++;        result[t2][1]++;
        dfs(tc, game + 1);
        result[t1][1]--;        result[t2][1]--;

        // t1 lose, t2 win
        result[t1][2]++;        result[t2][0]++;
        dfs(tc, game + 1);
        result[t1][2]--;        result[t2][0]--;

    }

    public static void main(String[] args) {
        // 백준_6987_월드컵
        // 정올_1841_월드컵
        Scanner sc = new Scanner(System.in);

        matrix = new int[6][3];
        result = new int[6][3];
        ans = new int[4];

        for (int tc = 0; tc < 4; tc++) {
            for (int i = 0; i < 6; i++) {
                for (int j = 0; j < 3; j++) {
                    matrix[i][j] = sc.nextInt();
                }
            }
            dfs(tc, 0);
        }

        for (int x : ans)
            System.out.print(x + " ");
        System.out.println();

        sc.close();
    }
}