[BaekJoon] 6987 월드컵 (Java)

1.  문제 링크

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

2.  문제

요약

• 월드컵 조별 최종 예선에서는 6개국으로 구성된 각 조별로 동일한 조에 소속된 국가들과 한 번씩, 각 국가별로 총 5번의 경기를 치릅니다.
• 조별리그가 끝난 후, 기자가 보내온 승, 무승부, 패의 수가 가능한 결과인지를 판별하려고 합니다.
• 네 가지의 결과가 주어질 때, 각각의 결과에 대하여 가능하면 1, 불가능하면 0을 출력하는 문제입니다.
• 입력: 첫 번째 줄부터 네 번째 줄까지 각 줄마다 6개국의 결과가 나라별로 승, 무승부, 패의 순서로 주어집니다. 승, 무, 패의 수는 0보다 크거나 같고 6보다 작거나 같은 정수입니다.
• 출력: 첫 번째 줄에 입력에서 주어진 네 가지 결과에 대하여 가능한 결과는 1, 불가능한 결과는 0을 빈칸을 하나 사이에 두고 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
	static int total_matches;
	static int[][] match_team;
	boolean possible = false;
	public boolean simulation(int[][] result, int round) {
		if(round == total_matches)
			return true;
		
		if(result[match_team[round][0]][0] > 0 && result[match_team[round][1]][2] > 0) {
			result[match_team[round][0]][0]--;
			result[match_team[round][1]][2]--;
			if(simulation(result, round + 1))
				return true;
			result[match_team[round][0]][0]++;
			result[match_team[round][1]][2]++;
		}
		if(result[match_team[round][0]][2] > 0 && result[match_team[round][1]][0] > 0) {
			result[match_team[round][0]][2]--;
			result[match_team[round][1]][0]--;
			if(simulation(result, round + 1))
				return true;
			result[match_team[round][0]][2]++;
			result[match_team[round][1]][0]++;
		}
		if(result[match_team[round][0]][1] > 0 && result[match_team[round][1]][1] > 0) {
			result[match_team[round][0]][1]--;
			result[match_team[round][1]][1]--;
			if(simulation(result, round + 1))
				return true;
			result[match_team[round][0]][1]++;
			result[match_team[round][1]][1]++;
		}
		return false;
	}
	
	public int isPossible(int[][] result) {
		for(int i = 0; i < result.length; i++) {
			int match_num = 0;
			for(int j = 0; j < result[i].length; j++) {
				match_num += result[i][j];
			}
			if(match_num != 5)
				return 0;
		}
		if(simulation(result, 0))
			return 1;
		else
			return 0;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		Main m = new Main();
		for(int i = 1; i < 6; i++) {
			total_matches += i;
		}
		int cur_match = 0;
		match_team = new int[total_matches][2];
		for(int i = 0; i < 5; i++) {
			for(int j = i + 1; j < 6; j++) {
				match_team[cur_match][0] = i;
				match_team[cur_match][1] = j;
				cur_match++;
			}
		}
		for(int i = 0; i < 4; i++) {
			int[][] result = new int[6][3];
			String[] input = br.readLine().split(" ");
			for(int j = 0; j < 6; j++) {				
				for(int l = 0; l < 3; l++) {
					result[j][l] = Integer.parseInt(input[3 * j + l]);
				}
			}
			bw.write(m.isPossible(result) + " ");
		}
		br.close();
		bw.flush();
		bw.close();
	}
}

4.  접근

• 총 6개의 팀이 서로 한 번씩, 즉 한 팀당 5번의 경기를 해야 하므로 전체 경기 수는
  • A - B, C, D, E, F
  • B - C, D, E, F
  • C - D, E, F
  • D - E, F
  • E - F
• 위와 같이 총 15번이 됩니다.
• 위 대진을 각각 match_team이라는 2차원 배열에 저장시키는데, 이 때 A는 0, B는 1, C는 2,... 이런 식으로 바꾸어 저장합니다.
• 만약 주어진 결과에서 각 팀의 승, 무, 패의 개수의 합이 5가 아니라면 각 팀당 5번 경기를 치뤄야 한다는 조건과 맞지 않으므로 0을 출력합니다.
• 이후, 백트래킹을 이용하여 가능한 결과인지 확인합니다.
• 배열 match_team에서 행이 몇 번째 경기인지를 의미하고 열이 경기하는 팀들을 의미합니다.
• 만약 match_team의 각 경기에서 열의 index가 0인 곳에 있는 팀과 열의 index가 1인 곳에 있는 팀에 대해 전자가 이기는 경우, 후자가 이기는 경우, 비기는 경우 각각에 대해 주어진 결과에서 맞는 위치에 있는 값을 1씩 줄이고 재귀함수 호출을 통해 각각의 경우를 확인하며 가능한 결과인지 확인합니다.
• 만약 재귀함수 호출을 진행하다가 현재의 경우가 가능한 결과가 아니라면 1씩 뺀 값을 다시 원래대로 돌려 백트래킹을 통해 다른 경우를 확인합니다.
• 재귀함수 호출의 종료는 현재까지의 경기의 수가 전체 경기 수인 15이면 재귀함수 호출을 종료합니다.