[BOJ] 6987. 월드컵 - JAVA

🔗 문제

 

 

👨🏻‍💻 풀이 및 코드

문제 유형 및 난이도 : 브루트포스, 백트랙킹 / G4

 

나한텐 좀 어려웠다. 처음엔 단순하게 한 개의 팀이 경기를 하는 횟수가 5여야 하고, 진 횟수와 이긴 횟수를 비교하고,  비긴 횟수가 짝수로 떨어지면 될 거라고 생각했는데 다른 사람들 해설을 참고하니 아예 접근 방식이 틀리고 완탐 + 백트랙킹으로 푸는 문제였다.   

 

일단 조건을 찬찬히 살펴보자.

총 6개의 팀이 있다.

A, B, C, D, E, F

 

한 번 경기를 치룬 팀과는 경기를 다시 치루지 않는다.

이 때 치르게 되는 총 경기의 횟수는 얼마일까?

A - B, C, D, E, F
B - C, D, E, F
C - D, E, F
D - E, F
E - F

 

이렇게  총 15번 이다. (5 + 4 + 3 + 2 + 1)

이 경우를 모두 반복문을 통해 탐색할 예정이다. 그리고, 한 개의 승부를 살펴보자. 한 개의 승부에선 3개의 결과가 나온다.

A 와 B 가 경기를 한다.

① A 승 / B 패
② A 무 / B 무
③ A 패 / B 승

 

총 15번의 경기를 치르면서 3개의 상황을 모두 체크한다.

만약, 입력으로 주어진 승패 점수 표가 이에 해당하지 않는다면  불가능한 결과로 판단한다.

 

이제 코드로 설계해보자.

static final int TEAM_NUMBER = 6;     // 총 6개의 팀이 참가한다.

int matchCount = 0;      			 // 총 경기의 수는 15이다. (5 + 4 + 3 + 2 + 1)
for(int i=1; i<TEAM_NUMBER; i++) {
   matchCount += i; 
}

// 경기의 A, B, C, D, E, F 를 각각 0, 1, 2, 3, 4, 5 로 바꿔서 match 에 담는다.
// match[0] = new int[] {0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 3, 3, 4};
// match[1] = new int[] {1, 2, 3, 4, 5, 2, 3, 4, 5, 3, 4, 5, 4, 5, 5};
// ex) matchCount[0][0] : 0, matchCount[0][1] : 1  -> 0번째엔 A와 B 가 경기한다.
int[][] match = new int[matchCount][2];
int idx=0;
for(int i=0; i<TEAM_NUMBER; i++) {
    for(int j=i+1; j<TEAM_NUMBER; j++) {
        match[idx][0] = i;
        match[idx++][1] = j;
    }
}

 

이제 경기까진 들어왔고 한 경기에 3가지 상황이 발생한다.

score 에는 입력으로 주어진 승무패의 횟수가 들어있는데, 0보다 큰 경우만 가능하다.

만약 15번의 경기까지 모두 무사히 치뤘다면 그 경우는 가능한 경우이다. 

static boolean play(int turn) {
	// 무사히 15개의 경기를 치뤘다면 가능한 결과
    if(turn == 15) {
        return true;
    }

    // turn번째 경기
    // ex) team1 = A, team2 = B
    int team1 = match[turn][0];
    int team2 = match[turn][1];

	// 입력으로 주어진 결과가 0보다 크다면
    if(score[team1][0] > 0 && score[team2][2] > 0) {
        score[team1][0]--;
        score[team2][2]--;
        if(play(turn+1)) return true;
        score[team1][0]++;
        score[team2][2]++;
    }

    // A 무 / B 무
    if(score[team1][1] > 0 && score[team2][1] > 0) {
        score[team1][1]--;
        score[team2][1]--;
        if(play(turn+1)) return true;
        score[team1][1]++;
        score[team2][1]++;
    }

    // A 패 / B 승
    if(score[team1][2] > 0 && score[team2][0] > 0) {
        score[team1][2]--;
        score[team2][0]--;
        if(play(turn+1)) return true;
        score[team1][2]++;
        score[team2][0]++;
    }

    return false;
}

 

해당 매커니즘의 시간 복잡도는 O(3^15) 이다. (1번의 경기당 3개의 결과가 있는데, 총 15개의 경기를 치르므로)

위 코드는 총 치뤄야 하는 경기의 갯수를 체크하진 못한다. 따라서, 각 팀이 치르는 경기의 수가 5가 아니면 불가능한 결과라는 조건을 추가해야 한다.

나머진 전체 코드를 보면 이해가 될 것 같다.

 

 

전체 코드

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

public class Main_bj_6987_월드컵 {
	
	static int[][] match;
	static final int TEAM_NUMBER = 6;
	static int[][] score;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		
		int matchCount = 0;		// 총 경기 횟수
		for(int i=1; i<TEAM_NUMBER; i++) {
			matchCount += i;
		}
		
		match = new int[matchCount][2];	 // i번째 경기 때 경기할 팀의 번호 ex)match[0][0] : A, match[0][1] : B => 0번째에 A와 B가 경기를 함.
		int idx=0;
		for(int i=0; i<TEAM_NUMBER; i++) {
			for(int j=i+1; j<TEAM_NUMBER; j++) {
				match[idx][0] = i;
				match[idx++][1] = j;
			}
		}
		
		score = new int[TEAM_NUMBER][3];	// [0]: 이긴 횟수, [1]: 비긴 횟수: [2]: 진 횟수
		
		for(int i=0; i<4; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int res = 1;
			
			for(int a=0; a<TEAM_NUMBER; a++) {
				int total=0;
				
				int win = score[a][0] = Integer.parseInt(st.nextToken());
				int draw = score[a][1] = Integer.parseInt(st.nextToken());
				int lose = score[a][2] = Integer.parseInt(st.nextToken());
				
				total += win + draw + lose;
				if(total != 5) {
					res = 0;
				}
			}
			
			if(res==1 && !play(0)) {
				res = 0;
			}
			
			sb.append(res).append(" ");
			
		}
		System.out.println(sb.toString());
		br.close();
		
	}
	
	static boolean play(int turn) {
		if(turn == 15) {
			return true;
		}
		
		// turn번째 경기
		// A 승 / B 패
		int team1 = match[turn][0];
		int team2 = match[turn][1];
		
		if(score[team1][0] > 0 && score[team2][2] > 0) {
			score[team1][0]--;
			score[team2][2]--;
			if(play(turn+1)) return true;
			score[team1][0]++;
			score[team2][2]++;
		}
		
		// A 무 / B 무
		if(score[team1][1] > 0 && score[team2][1] > 0) {
			score[team1][1]--;
			score[team2][1]--;
			if(play(turn+1)) return true;
			score[team1][1]++;
			score[team2][1]++;
		}
		
		// A 패 / B 승
		if(score[team1][2] > 0 && score[team2][0] > 0) {
			score[team1][2]--;
			score[team2][0]--;
			if(play(turn+1)) return true;
			score[team1][2]++;
			score[team2][0]++;
		}
		
		return false;
	}

}

 

---

Reference

• https://maivve.tistory.com/215
• https://velog.io/@hyeon930/BOJ-6987-%EC%9B%94%EB%93%9C%EC%BB%B5-Java