[ 백준 ] 6987번 월드컵 (Java 자바)

🔗 문제 링크: 백준 17281번 - 야구

문제 설명

월드컵 조별 최종 예선에서는 6개국으로 구성된 각 조별로 동일한 조에 소속된 국가들과 한 번씩, 각 국가별로 총 5번의 경기를 치른다. 조별리그가 끝난 후, 기자가 보내온 각 나라의 승, 무승부, 패의 수가 가능한 결과인지를 판별하려고 한다. 다음은 가능한 결과와 가능하지 않은 결과의 예이다.

네 가지의 결과가 주어질 때 각각의 결과에 대하여 가능하면 1, 불가능하면 0을 출력하는 프로그램을 작성하시오.

입력 조건

• 각 테스트 케이스:
  • 6개 팀의 결과가 6행 3열 배열 형태로 주어진다.
  • 각 행은 한 팀의 결과를 의미하며, [승, 무, 패]의 순서로 3개의 정수가 주어진다.
• 총 4개의 테스트 케이스가 주어진다.

---

풀이 과정

📌 문제 요약

• 6개 팀이 치른 15경기의 결과를 모든 가능한 경기 결과 조합(승/무/패)을 고려하여 재구성한다.
• 각 팀의 경기 결과가 주어진 값과 일치하는지 DFS와 백트래킹을 통해 확인한다.
• 미리 15경기의 조합을 배열에 저장하여, DFS에서 순서대로 경기를 처리한다.

📌 해결 전략

1. 15경기 조합 사전 계산:
   • 6개 팀 중 두 팀씩 골라 경기를 치르는 모든 조합은 총 15경기가 된다.
   • 이를 배열 games에 미리 저장해 두어, DFS에서 경기 순서를 정해놓고 처리할 수 있게 한다.
2. 기본 유효성 검사:
   • 각 팀의 경기 수가 5경기인지, 전체 승수와 패수가 일치하는지, 무승부의 개수가 짝수인지를 미리 체크한다.
   • 기본 조건이 충족되지 않으면 DFS를 진행하지 않고 바로 불가능한 결과로 판단한다.
3. DFS와 백트래킹:
   • DFS를 15경기에 대해 순서대로 처리하며, 각 경기마다 세 가지 경우(팀 A 승/팀 B 패, 무승부, 팀 A 패/팀 B 승)를 시도한다.
   • 해당 경기의 결과에 대해 각 팀의 남은 승, 무, 패 수가 충분한 경우에만 선택하고, 선택 후에는 그 값을 감소시킨다.
   • DFS가 모든 15경기를 처리하면 가능한 결과로 판별하고, 재귀 호출이 끝난 후에는 반드시 원래 값으로 복구(백트래킹)하여 다른 경우의 수를 탐색한다.

📌 풀이 과정

• 경기 순서 고정의 이유:
  미리 15경기의 팀 조합을 배열 games에 저장하면, DFS에서 경기 순서를 일정하게 유지할 수 있다.
  이렇게 하면 "어떤 경기부터 처리할지"에 대한 고민 없이, 순서대로 결과를 채워 넣으면서 재귀 호출을 진행할 수 있다.
• 경우의 수 선택(세 가지 분기) 이유:
  각 경기는 세 가지 결과가 가능하다.
  • 경우 1: 팀 A가 승리하면 팀 A의 승 수가 1 감소하고, 팀 B의 패 수가 1 감소해야 한다.
  • 경우 2: 무승부인 경우 두 팀의 무 수가 각각 1 감소한다.
  • 경우 3: 팀 B가 승리하면 팀 B의 승 수가 1 감소하고, 팀 A의 패 수가 1 감소해야 한다.
    이 세 가지 경우를 DFS의 각 분기마다 시도하며, 조건에 맞지 않는 경우는 해당 분기를 건너뛰도록 했다.
• 백트래킹의 중요성:
  한 번의 선택으로 인해 결과 배열(arr)의 값이 변경되면, 이후 다른 경기 결과를 탐색할 때 영향을 주게 된다.
  따라서 DFS 재귀 호출이 끝난 후, 선택했던 값을 다시 원래대로 복구(증가시키는 형태로)하여 다른 경우의 수를 올바르게 탐색하도록 한다.
• 조기 종료:
  DFS 과정 중 이미 가능한 결과가 발견되면(possible 플래그가 true로 설정되면) 더 이상 불필요한 탐색을 진행하지 않도록 조기 종료시켜, 시간 효율성을 높인다.

📌 시간 복잡도 분석

• DFS의 깊이는 15(경기의 수)이며, 각 경기는 세 가지 경우의 수를 가진다.
• 최악의 경우 시간 복잡도는 O(3^15)이지만, 기본 유효성 검사와 백트래킹(불필요한 분기 제거)을 통해 실제 탐색하는 경우의 수는 훨씬 줄어든다.
• 테스트 케이스가 4개이므로, 전체적으로 충분히 처리 가능한 범위이다.

---

🔥 최종 정리 및 코드

미리 15경기의 조합을 구해두고, DFS와 백트래킹을 통해 각 경기에서 가능한 결과를 순서대로 채워 나간다.
각 분기마다 선택한 결과에 따라 팀의 남은 승, 무, 패 수를 감소시키고, 조건에 부합하는지 확인한다.
DFS 재귀가 끝나면 선택했던 값을 복구하여 다른 경우의 수를 탐색한다.
이러한 핵심 로직 덕분에, 모든 15경기의 결과를 탐색하면서 주어진 결과와 일치하는지 판별할 수 있다.

 

package Graph;

import java.io.*;
import java.util.StringTokenizer;

/*
    BOJ 6987 Gold4, 월드컵
    문제 링크: https://www.acmicpc.net/problem/6987

    [핵심 아이디어]
    - 6개 팀의 결과를 6×3 배열로 입력받는다. (각 팀의 승, 무, 패)
    - 6팀이 서로 한 번씩 경기를 치르는 총 15경기의 팀 조합을 미리 구해 games 배열에 저장한다.
    - DFS를 통해 각 경기에서 세 가지 경우(팀 A 승/팀 B 패, 무승부, 팀 A 패/팀 B 승)를 순서대로 시도한다.
    - 각 분기에서 해당 경기의 결과를 반영하기 위해, 팀의 승, 무, 패 개수를 감소시키고 DFS를 진행하며, 재귀 종료 후 반드시 복구(백트래킹)한다.
    - 모든 15경기를 처리하면 가능한 결과로 판별하여 플래그를 true로 설정한다.
    - 기본 유효성 검사를 통해 경기 수, 전체 승수/패수, 무승부 개수 등의 조건을 미리 체크한다.
*/

public class BOJ_G4_6987 {
    // 15경기의 팀 조합 (6팀 중 2팀씩 고르는 조합)
    static int[][] games = new int[15][2];
    // 각 테스트 케이스별 팀 결과: [팀][0:승, 1:무, 2:패]
    static int[][] arr;
    // 가능한 결과인지 판별하는 플래그
    static boolean possible;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        // 미리 15경기의 조합을 구함 (6팀 중 모든 두 팀의 조합)
        int index = 0;
        for (int i = 0; i < 6; i++) {
            for (int j = i + 1; j < 6; j++) {
                games[index][0] = i;
                games[index][1] = j;
                index++;
            }
        }

        // 4개의 테스트 케이스 처리
        for (int t = 0; t < 4; t++) {
            arr = new int[6][3];
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int i = 0; i < 6; i++) {
                for (int j = 0; j < 3; j++) {
                    arr[i][j] = Integer.parseInt(st.nextToken());
                }
            }
            // 기본 유효성 검사: 각 팀의 경기수 5, 전체 승수와 패수가 동일, 무승부 개수는 짝수여야 함.
            if (!isValid(arr)) {
                sb.append("0 ");
                continue;
            }
            possible = false;
            dfs(0);
            sb.append(possible ? "1 " : "0 ");
        }
        System.out.println(sb.toString().trim());
    }

    // 각 팀의 경기 수와 전체 승, 무, 패 결과가 기본 조건을 만족하는지 검사
    static boolean isValid(int[][] arr) {
        int sumWins = 0, sumDraws = 0, sumLosses = 0;
        for (int i = 0; i < 6; i++) {
            if (arr[i][0] + arr[i][1] + arr[i][2] != 5) return false;
            sumWins += arr[i][0];
            sumDraws += arr[i][1];
            sumLosses += arr[i][2];
        }
        if (sumWins != sumLosses) return false;
        if (sumDraws % 2 != 0) return false;
        return true;
    }

    // DFS 함수: matchIndex는 현재까지 처리한 경기 수 (0 ~ 15)
    static void dfs(int matchIndex) {
        // 이미 가능한 결과를 찾았다면 조기 종료 (효율성 향상)
        if (possible) return;
        // 모든 15경기를 처리하면 가능한 결과임
        if (matchIndex == 15) {
            possible = true;
            return;
        }
        int teamA = games[matchIndex][0];
        int teamB = games[matchIndex][1];

        // 경우 1: 팀 A 승 / 팀 B 패
        if (arr[teamA][0] > 0 && arr[teamB][2] > 0) {
            arr[teamA][0]--;
            arr[teamB][2]--;
            dfs(matchIndex + 1);
            arr[teamA][0]++;
            arr[teamB][2]++;
        }
        // 경우 2: 무승부
        if (arr[teamA][1] > 0 && arr[teamB][1] > 0) {
            arr[teamA][1]--;
            arr[teamB][1]--;
            dfs(matchIndex + 1);
            arr[teamA][1]++;
            arr[teamB][1]++;
        }
        // 경우 3: 팀 A 패 / 팀 B 승
        if (arr[teamA][2] > 0 && arr[teamB][0] > 0) {
            arr[teamA][2]--;
            arr[teamB][0]--;
            dfs(matchIndex + 1);
            arr[teamA][2]++;
            arr[teamB][0]++;
        }
    }
}