[BJ6987] 월드컵

🚩 문제 설명

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

6987번: 월드컵

 

 

 

---

 

 

 

✅ 입출력

변수 설명
return ➡️ 해당 결과표가 가능한지, 불가능한지

✔️ 예제 1

5 0 0 3 0 2 2 0 3 0 0 5 4 0 1 1 0 4
4 1 0 3 0 2 4 1 0 1 1 3 0 0 5 1 1 3
5 0 0 4 0 1 2 2 1 2 0 3 1 0 4 0 0 5
5 0 0 3 1 1 2 1 2 2 0 3 0 0 5 1 0 4

1 1 0 0

 

 

 

---

 

 

 

📑 문제 풀이

with 자바 (Java)

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


public class Main {
	static final int T = 4, N = 6, M = 3;

	static int ans;
	static boolean flag;

	static int[] team1 = new int[15];
	static int[] team2 = new int[15];
	static int[] win = new int[N];
	static int[] draw = new int[N];
	static int[] lose = new int[N];


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

		// 6C2 = 15
		// [0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 3, 3, 4]
		// [1, 2, 3, 4, 5, 2, 3, 4, 5, 3, 4, 5, 4, 5, 5]
		// 총 2개의 팀이 30개의 승무패가 난다.
		int idx = 0;
		for (int i = 0; i < 5; i++) {
			for (int j = i + 1; j < 6; j++) {
				team1[idx] = i;
				team2[idx] = j;
				idx++;
			}

		}

		for (int t = 0; t < T; t++) {
			StringTokenizer st = new StringTokenizer(br.readLine());

			int sum = 0;
			for (int i = 0; i < N; i++) {
				// win: [5, 3, 2, 0, 4, 1]
				// draw: [0, 0, 0, 0, 0, 0]
				// lose: [0, 2, 3, 5, 1, 4]

				win[i] = Integer.parseInt(st.nextToken());
				draw[i] = Integer.parseInt(st.nextToken());
				lose[i] = Integer.parseInt(st.nextToken());

				sum += win[i] + draw[i] + lose[i];
			}

			flag = false;
			if (sum == 30) dfs(0);

			// 출력
			if (flag) System.out.print(1 + " ");
			else System.out.print(0 + " ");

			break;

		}

	} // end main


	private static void dfs(int dep) {
		if (flag) return; // 가지 치기

		// 15번 경기를 다 치뤘으면
		if (dep == 15) {
			flag = true;
			return;
		}

		// 겨루는 나라 2개
		int t1 = team1[dep];
		int t2 = team2[dep];

		// t1 win
		if (win[t1] > 0 && lose[t2] > 0) {
			win[t1]--;
			lose[t2]--;
			dfs(dep + 1);
			win[t1]++;
			lose[t2]++;
		}

		// t1 draw t2
		if (draw[t1] > 0 && draw[t2] > 0) {
			draw[t1]--;
			draw[t2]--;
			dfs(dep + 1);
			draw[t1]++;
			draw[t2]++;
		}

		// t1 lose
		if (lose[t1] > 0 && win[t2] > 0) {
			lose[t1]--;
			win[t2]--;
			dfs(dep + 1);
			lose[t1]++;
			win[t2]++;
		}

	} // end dfs

}

💬 Point

➡️  겨루는 팀을 나눠서 dep 마다 꺼낸다.
➡️  승, 무, 패 에 따라 백트랙킹한다.

 

// 6C2 = 15
// [0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 3, 3, 4]
// [1, 2, 3, 4, 5, 2, 3, 4, 5, 3, 4, 5, 4, 5, 5]
// 총 2개의 팀이 30개의 승무패가 난다.
int idx = 0;
for (int i = 0; i < 5; i++) {
    for (int j = i + 1; j < 6; j++) {
        team1[idx] = i;
        team2[idx] = j;
        idx++;
    }

}

◾ 승패를 겨루는 경우의 수를 구한다.

◾ (A, B, C, D, E, F) 의 나라에서 2 팀씩 꺼내는 조합과도 같다.

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

 

private static void dfs(int dep) {
    if (flag) return; // 가지 치기

    // 15번 경기를 다 치뤘으면
    if (dep == 15) {
        flag = true;
        return;
    }

    // 겨루는 나라 2개
    int t1 = team1[dep];
    int t2 = team2[dep];

    // t1 win
    if (win[t1] > 0 && lose[t2] > 0) {
        win[t1]--;
        lose[t2]--;
        dfs(dep + 1);
        win[t1]++;
        lose[t2]++;
    }

    // t1 draw t2
    if (draw[t1] > 0 && draw[t2] > 0) {
        draw[t1]--;
        draw[t2]--;
        dfs(dep + 1);
        draw[t1]++;
        draw[t2]++;
    }

    // t1 lose
    if (lose[t1] > 0 && win[t2] > 0) {
        lose[t1]--;
        win[t2]--;
        dfs(dep + 1);
        lose[t1]++;
        win[t2]++;
    }

} // end dfs

◾ 15 번의 경기를 치뤄야하기 때문에, dep 가 15번까지 가야한다.

◾ 만약 15번의 경기를 치루지 않았다면, 해당 결과표는 불가능하다.

◾ 이기고 지고의 백트랙킹을 타고 넘어간다.

◾ 만약 t1이 승을 거뒀다면 t2은 패를 하게 된다. 따라서 둘은 동시에 빠진다.

 

 

 

 

 

 

 

 

 

 

 

# 백준 월드컵 java

# 백준 월드컵 자바

---