[JAVA] 백준 6987 - 월드컵

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

 

 

 

처음에 스스로 풀었을때는 통과하긴 했지만 2000ms나 걸렸다.

 

처음 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;

public class Main {

    static int[][] ans;
    static int[][] check;
    static boolean correct;
    static ArrayList<Point> list = new ArrayList<>();
    static LinkedList<Integer> set = new LinkedList<>();
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        dfs(0, 0);

        for (int i = 0; i < 4; i++) {
            ans = new int[6][3];
            check = new int[6][3];
            correct = false;
            String[] lines = br.readLine().split(" ");
            int count = 0;
            for(int x = 0 ; x < 6 ; x++){
                for(int y = 0 ; y < 3 ; y++){
                    check[x][y] = Integer.parseInt(lines[count++]);
                }
            }
            dfs2(0);
            if(correct){
                System.out.print("1 ");
            }else{
                System.out.print("0 ");
            }
        }
//        System.out.println(list);
    }

    static void dfs(int depth, int count) {
        if (count == 2) {
            list.add(new Point(set.get(0), set.get(1)));
            return;
        }

        for (int i = depth; i < 6; i++) {
            set.push(i);
            dfs(i + 1, count + 1);
            set.poll();
        }
    }
    static void dfs2(int count){
        if(correct) return;
        if(count == 15){
            check();
            return;
        }
        Point p = list.get(count);
        int me = p.x;
        int opponent = p.y;
        for(int i = 0 ; i < 3 ; i++){
            ans[me][i] ++;
            ans[opponent][2 - i] ++;
            dfs2(count + 1);
            ans[me][i] --;
            ans[opponent][2 - i] --;
        }


    }
    static void check(){
        boolean flag = true;
        for(int i = 0 ; i < 6 ; i++){
            for(int j = 0 ; j < 3 ; j++){
                if(ans[i][j] != check[i][j]) flag = false;
            }
//            System.out.println();
        }
        if(flag) correct = true;
    }
}

class Point {
    int x;
    int y;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public String toString(){
        return "(" + x + "," + y +")";
    }
}

 

 

로직은 6C2의 조합을 모두 list에 넣어두고, 해당 list를 dfs로 반복하여 승/무/패 로 완전탐색을 하고(백트래킹),

최종 결과를 ans[6][3]에 저장해두었다가 check()에서 입력 값과 비교를 한후, 전부다 같으면 correct를 true로 바꾸는 로직인데,

이 경우 가지치기가 없어서 굳이 탐색안해도되는 경로를 모두 탐색한다. (그래도 2000ms는 나오는것으로 보아 통과는 하게 만들어 둔 모양이다..)

 

 

 

개선된 코드

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;

public class Main {

    static int[][] check;
    static boolean correct;
    static ArrayList<Point> list = new ArrayList<>();
    static LinkedList<Integer> set = new LinkedList<>();
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        dfs(0, 0);

        for (int i = 0; i < 4; i++) {
            check = new int[6][3];
            correct = false;
            String[] lines = br.readLine().split(" ");
            int count = 0;
            for(int x = 0 ; x < 6 ; x++){
                for(int y = 0 ; y < 3 ; y++){
                    check[x][y] = Integer.parseInt(lines[count++]);
                }
            }
            dfs2(0);
            if(correct){
                System.out.print("1 ");
            }else{
                System.out.print("0 ");
            }
        }
    }

    static void dfs(int depth, int count) {
        if (count == 2) {
            list.add(new Point(set.get(0), set.get(1)));
            return;
        }

        for (int i = depth; i < 6; i++) {
            set.push(i);
            dfs(i + 1, count + 1);
            set.poll();
        }
    }

    static void dfs2(int count){
        if(correct) return;
        if(count == 15){
            check();
            return;
        }
        Point p = list.get(count);
        int me = p.x;
        int opponent = p.y;
        for(int i = 0 ; i < 3 ; i++){
            if(check[me][i] == 0 || check[opponent][2 - i] == 0) continue;
            check[me][i] --;
            check[opponent][2 - i] --;
            dfs2(count + 1);
            check[me][i] ++;
            check[opponent][2 - i] ++;
        }


    }
    static void check(){
        boolean flag = true;
        for(int i = 0 ; i < 6 ; i++){
            for(int j = 0 ; j < 3 ; j++){
                if(check[i][j] > 0) flag = false;
            }
        }
        if(flag) correct = true;
    }
}

class Point {
    int x;
    int y;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public String toString(){
        return "(" + x + "," + y +")";
    }
}

 

 

로직은 완전히 똑같지만, ans[6][3]에 기록해두는게아니라, 애초에 입력 값을 check[6][3]에 기록해두었다가, 거기서 하나씩 빼가며 경우의 수를 탐색하는것이다. 예를들어 (A,B)의 경기에서 A가 승이면, check[A][0]에서 1을 빼고, check[B][2]에서 1을 뺴는것이다.. check()에서 결과를 판단할때는 check[6][3]이 모두 0인지만 체크하면 된다 (0일경우 correct) 

 

이렇게 변경했을때 이점이 무엇이냐면 check[i][j] == 0 인경우 , 애초에 승부가 성립하지 않으므로, 가지치기를 할수가있다.

쓸데없는 호출을 줄일수있다.. 

 

 

성능 비교

 

 

 

20배나 성능차이가 난다