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

💡문제 분석 요약

월드컵 조별 리그의 결과를 입력받아, 입력받은 결과가 가능한지 아닌지 판별하는 문제이다.

• 시간 제한: 1초
• 메모리 제한: 128MB

 

💡알고리즘 설계

• 문제 조건
  • 한 팀의 경기 수는 5회
  • 각 팀은 다른 모든 팀과 한 번씩 경기 ⇒ 총 15경기
  • 각 경기 결과는 승-패, 무-무, 패-승 중 하나 ⇒ 총 3가지
• 자료구조
  • int[] team1, int[] team2: 각 라운드별 경기를 진행하는 팀
  • int[][] gameInputResult: 입력받은 각 팀의 경기 결과(승,무,패) 횟수
  • int[][] gameResult: 백트래킹 과정에서 계산하는 각 팀의 경기 결과 횟수
  • int[] result: 각 테스트 케이스의 결과를 저장하는 배열
• 백트래킹
  • 라운드 0부터 시작해서 각 경기 결과를 가정하며 탐색
  • 각 라운드에서 3가지 경우를 순차적으로 시도. (경기 결과: 승-패, 무-무, 패-승)
    • 각 경우마다 gameResult 업데이트
    • 다음 라운드로 재귀 호출하여 탐색
    • 재귀 호출 후 gameResult 원상 복구 (백트래킹)
    • 유효하지 않은 경로는 자동으로 백트래킹되어 다음 경우로 넘어감
  • 모든 경기가 끝났을 때 (round == 15)
    • gameResult가 gameInputResult 와 일치하는지 확인

 

💡코드

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

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[][] gameInputResult;
    static int[][] gameResult;
    static int[] result = new int[4];
    static StringBuilder sb = new StringBuilder();

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

        for(int i=0; i<4; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            gameInputResult = new int[6][3];
            gameResult = new int[6][3];
            for(int j=0; j<6; j++) {
                for(int k=0; k<3; k++) {
                    gameInputResult[j][k] = Integer.parseInt(st.nextToken());
                }
            }
            backtracking(i, 0);
            sb.append(result[i]+" ");
        }

        System.out.println(sb);
    }

    static void backtracking(int i, int round) {
        if(result[i]==1) return;
        if(round == 15) {
            for(int t=0; t<6; t++) {
                for(int k=0; k<3; k++) {
                    if(gameInputResult[t][k] != gameResult[t][k])
                        return;
                }
            }
            result[i] = 1;
            return;
        }

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

        // 승-패
        gameResult[t1][0]++; gameResult[t2][2]++;
        backtracking(i, round+1);
        gameResult[t1][0]--; gameResult[t2][2]--;

        // 무-무
        gameResult[t1][1]++; gameResult[t2][1]++;
        backtracking(i, round+1);
        gameResult[t1][1]--; gameResult[t2][1]--;

        // 패-승
        gameResult[t1][2]++; gameResult[t2][0]++;
        backtracking(i, round+1);
        gameResult[t1][2]--; gameResult[t2][0]--;
    }
}

 

💡시간복잡도

각 경기마다 3가지 경우를 고려하므로 $O(3^{15})$이다.

 

💡 틀린 이유

원래 백트래킹 과정에서 if(gameInputResult[t1][0] > 0 && gameInputResult[t2][2] > 0) 조건을 사용했다.

이 조건은 현재 입력된 결과(gameInputResult)에 따라 백트래킹을 진행할지 결정한다. 하지만 이렇게 하면 모든 가능한 경우를 고려할 수 없다.

예를 들어, 현재 단계에서는 조건을 만족하지 않지만, 이후의 백트래킹 과정에서 유효한 결과가 나올 수 있는 경우를 제외시킨다.

결과적으로 일부 유효한 케이스를 놓치게 되어 오답이 발생하게 된다.

 

💡 틀린 부분 수정

틀린 코드

// 승, 패
if(gameInputResult[t1][0] > 0 && gameInputResult[t2][2] > 0) {
    gameResult[t1][0]++; gameResult[t2][2]++; 
    backtracking(i, round+1);
    gameResult[t1][0]--; gameResult[t2][2]--; 
}
...

 

수정한 코드

// 승-패
gameResult[t1][0]++; gameResult[t2][2]++;
backtracking(i, round+1);
gameResult[t1][0]--; gameResult[t2][2]--;
...

 

REF) https://velog.io/@topqr123q/백준-6987번-자바

 

💡 느낀점 or 기억할정보

문제의 난이도가 높아서, 어떻게 풀어야 할지 스스로 생각해내지 못했다ㅠ 다른 사람의 풀이를 찾아보면서 진행했지만 아직도 완벽히 이해하지는 못한 것 같다. 이 문제보다 난이도가 낮은 백트래킹 문제를 더 풀어보고, 다시 한 번 시도해봐야겠다.

백트래킹에서 조건을 일찍 체크하면 유효한 해를 놓칠 수 있기 때문에 가능한 모든 경로를 탐색한 후, 최종 결과를 확인해야 한다!