BOJ_6987 : 월드컵

👉 문제링크

6987번: 월드컵

---

---

🔸 문제 분석 🔸

• 월드컵에서 6개의 국가가 서로 1번씩 경기를 뛰고 나온 결과로 가능한지 불가능한지 판단한다.
  • 4번의 경기 결과가 주어지는데, 한 나라의 승, 무, 패의 수로 입력된다.
  • 가능한 결과이면 1, 불가능한 결과이면 0을 반환한다.
• 6개의 국가에서 경기를 뛰는 경우의 수는 6C2 = 6*5/2 = 15개 이다.
  • 승/무/패 상관없이 총 15번의 경기가 가능하면, 올바른 경기 결과이다.
• 입력 제한이 0~6 이므로, 한 국가의 승무패의 합이 5가 되는지 확인해야 한다.
• 15번의 경기를 진행하며 경기 결과에서 1씩 빼는 방식으로 역 추적한다.
  • 15번 모두 확인 가능해야 한다. (모두 0이 되어야한다)

🔸 코드 🔸

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static final int SIZE = 15, COUNTRY = 6, GAME = 4;
    static int[][] matches, wc_result;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        matches = new int[SIZE][2];
        int idx = 0;
        for (int i = 0; i < COUNTRY - 1; i++) {
            for (int j = i + 1; j < COUNTRY; j++) {
                matches[idx][0] = i;
                matches[idx][1] = j;
                idx++;
            }
        }

        for (int i = 0; i < GAME; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            wc_result = new int[COUNTRY][3]; // win, draw, lose
            boolean flag = true;

            for (int j = 0; j < COUNTRY; j++) {
                int w = wc_result[j][0] = Integer.parseInt(st.nextToken());
                int d = wc_result[j][1] = Integer.parseInt(st.nextToken());
                int l = wc_result[j][2] = Integer.parseInt(st.nextToken());
                if (w + d + l != COUNTRY - 1)
                    flag = false;
            }

            if (flag && worldCup(0)) {
                System.out.print(1 + " ");
            } else
                System.out.print(0 + " ");
        }
    }

    private static boolean worldCup(int idx) {
        if (idx == SIZE) return true;

        int a_country = matches[idx][0];
        int b_country = matches[idx][1];

        if (wc_result[a_country][0] > 0 && wc_result[b_country][2] > 0) { // a승, b패
            wc_result[a_country][0]--;
            wc_result[b_country][2]--;
            if(worldCup(idx + 1)) return true;
            wc_result[a_country][0]++;
            wc_result[b_country][2]++;
        }

        if (wc_result[a_country][1] > 0 && wc_result[b_country][1] > 0) { // 무승부
            wc_result[a_country][1]--;
            wc_result[b_country][1]--;
            if(worldCup(idx + 1)) return true;
            wc_result[a_country][1]++;
            wc_result[b_country][1]++;
        }

        if (wc_result[a_country][2] > 0 && wc_result[b_country][0] > 0) { // a패, b승
            wc_result[a_country][2]--;
            wc_result[b_country][0]--;
            if(worldCup(idx + 1)) return true;
            wc_result[a_country][2]++;
            wc_result[b_country][0]++;
        }
        return false;
    }
}

🔸 코드 해석 🔸

• 나라의 수 COUNTRY, 경기 결과 수 GAME, 6개 중 2개를 뽑는 조합 수 SIZE를 저장해둔다.
• 2차원 배열 matches에는 15가지 매치 방법(몇 번 나라가 몇 번 나라와 경기하는지)을 저장하고,
  wc_result는 입력되는 4번의 경기 결과를 한 번씩 승,무,패로 나눠 저장한다.
  • 한 나라의 승,무,패의 합이 5가 아니라면 0을 출력한다.
• worldCup() 메서드는 0번 경기부터 15번 경기까지 진행 가능하면 true를 반환한다.
  • 한 경기에서 두 나라의 결과를 승,무,패로 나눠 각각 재귀로 넣는다.
  • 만약 승,무,패 모두 불가능하면 false를 반환한다.(백트래킹)
  • true는 연속으로 반환해서 즉시 종료할 수 있도록 한다.
• woldCup() 의 결과가 true이면 1을 출력한다.

---

🔸 end 🔸

• 상태가 안좋을때 풀었더니 초반 문제 분석도 엉망이었고, 디버깅도 제대로 하지 못했다.
  • 멘탈이 터져서 아주 조금씩 수정하고, 계속 틀렸습니다만 반복했다(11%의 지옥)
  • 너무 생각없이 운으로 통과되길 바란 것 같다.
• 다른 풀이 포스팅을 참고했고, 후에 다시 한 번 풀어보았다.
  • 코딩 계획을 적어가며 풀이했다.