[백준] 6987번: 월드컵 - java

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

public class Main {

	/**
	 * 기자가 보내온 각 나라의 승,무,패 결과 scores[i][j] -> i는 0~5까지이며 각각 "A~F" 를 의미한다. 
	 * -> j는 0,1,2로 각각 "승, 무, 패" 를 의미한다.
	 */
	static int[][] scores = new int[6][3];

	static int isPossible;
    	// i번째 경기에 출전하는 두 나라를 각각 aTeam, bTeam 에 저장한다.
	static int[] aTeam = { 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 3, 3, 4 }; 
	static int[] bTeam = { 1, 2, 3, 4, 5, 2, 3, 4, 5, 3, 4, 5, 4, 5, 5 };

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		for (int tc = 0; tc < 4; tc++) {
			st = new StringTokenizer(br.readLine());
			isPossible = 1;
			for (int i = 0; i < 6; i++) {
				scores[i][0] = Integer.parseInt(st.nextToken()); // 승
				scores[i][1] = Integer.parseInt(st.nextToken()); // 무
				scores[i][2] = Integer.parseInt(st.nextToken()); // 패

				// 각 나라별 무,승,부 합이 5가 아니라면 
				if (scores[i][0] + scores[i][1] + scores[i][2] != 5) {
					isPossible = 0;
					break;
				}
			}

			if (isPossible == 1) {
				isPossible = 0;
				match(0);
			}
			sb.append(isPossible).append(" ");
		}
		System.out.println(sb.toString());
	}

	static void match(int cnt) {
		if (cnt == 15) { // 모든 나라에 대해 승부 판별 완료 => 가능한 결과
			isPossible = 1;
			return;
		}
		if (isPossible == 0) { // 아직 판별이 안된경우에만 계속해서 탐색하기
			// start가 이길 경우
			if (scores[aTeam[cnt]][0] > 0 && scores[bTeam[cnt]][2] > 0) {
				scores[aTeam[cnt]][0]--;
				scores[bTeam[cnt]][2]--;
				match(cnt + 1);
				scores[aTeam[cnt]][0]++;
				scores[bTeam[cnt]][2]++;
			}
			// 무승부
			if (scores[aTeam[cnt]][1] > 0 && scores[bTeam[cnt]][1] > 0) {
				scores[aTeam[cnt]][1]--;
				scores[bTeam[cnt]][1]--;
				match(cnt + 1);
				scores[aTeam[cnt]][1]++;
				scores[bTeam[cnt]][1]++;
			}
			// start가 질 경우
			if (scores[aTeam[cnt]][2] > 0 && scores[bTeam[cnt]][0] > 0) {
				scores[aTeam[cnt]][2]--;
				scores[bTeam[cnt]][0]--;
				match(cnt + 1);
				scores[aTeam[cnt]][2]++;
				scores[bTeam[cnt]][0]++;
			}
		}
	}

}

 

DFS 를 이용한 백트래킹 방법이다.

모든 나라는 자신을 제외한 5개의 나라와 경기를 하므로, 총 경기 수는 

A:B~F / B:C~F / C:D~F / D:E~F / E:F 로 총 15경기가 될 것이다.

 

* 조건1

각 나라는 모두 5경기를 진행해야 한다.

	if (scores[i][0] + scores[i][1] + scores[i][2] != 5) {
			isPossible = 0;
			break;
	}

 

* 조건2

따라서 15경기에 대해서 DFS 가 끝까지 진행한 경우라면, 기자가 보낸 결과표가 가능함을 의미할 것이다.

구현의 편리함을 위해 15경기를 진행하는 순서를 미리 aTeam, bTeam 에 저장하였다.
static int[] aTeam = { 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 3, 3, 4 }; 
static int[] bTeam = { 1, 2, 3, 4, 5, 2, 3, 4, 5, 3, 4, 5, 4, 5, 5 };

 

DFS

기저조건 : cnt가 15인 경우

	if (cnt == 15) { // 모든 나라에 대해 승부 판별 완료 => 가능한 결과
		isPossible = 1;
		return;
	}

cnt번째 경기에 대해서 aTeam이 이긴 경우, 진 경우, 무승부인 경우를 생각해야 한다.

이때, 기자의 결과표와 대조해서, 남아 있는 "승 무 패" 개수가 1이상일 경우에만 (가지치기) , 재귀 호출이 가능하다.

			// start가 이길 경우
			if (scores[aTeam[cnt]][0] > 0 && scores[bTeam[cnt]][2] > 0) {
				scores[aTeam[cnt]][0]--;
				scores[bTeam[cnt]][2]--;
				match(cnt + 1);
				scores[aTeam[cnt]][0]++;
				scores[bTeam[cnt]][2]++;
			}
			// 무승부
			if (scores[aTeam[cnt]][1] > 0 && scores[bTeam[cnt]][1] > 0) {
				scores[aTeam[cnt]][1]--;
				scores[bTeam[cnt]][1]--;
				match(cnt + 1);
				scores[aTeam[cnt]][1]++;
				scores[bTeam[cnt]][1]++;
			}
			// start가 질 경우
			if (scores[aTeam[cnt]][2] > 0 && scores[bTeam[cnt]][0] > 0) {
				scores[aTeam[cnt]][2]--;
				scores[bTeam[cnt]][0]--;
				match(cnt + 1);
				scores[aTeam[cnt]][2]++;
				scores[bTeam[cnt]][0]++;
			}
		}