[백준] 6987 월드컵 - 브루트포스(BruteForce) + 조합(Combination) JAVA

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

6987번: 월드컵

코드설명

브루트포스(BruteForce) + 조합(Combination) 문제입니다.

 

문제에서 이해해야할점은,

1. 6팀이서 경기를 하는데 서로 5번씩 경기를 한다. 그러니 총 15번을 할 것입니다. 

이 문제에서는 6팀이서 경기를 하므로 무조건 15번씩의 경기를 진행할 것 입니다.

public static int[][] gameMatch = { {0,1}, {0, 2}, {0,3}, {0,4}, {0,5}, {1, 2}, {1, 3}, {1, 4}, {1, 5}, {2, 3}, {2, 4}, {2, 5}, {3, 4}, {3, 5}, {4, 5}};

만약에 6팀이 아닌, 100팀이 주어졌다고 가정하면, 조합을 구하는 코드를 DFS를 통해 구하여 Node를 만든뒤 ArrayList.add 하여 경기의 조합을 사용하면 될 것 입니다.

위의 처럼 간단하게 먼저 경기의 조합수가 고정되었을때는 위와 같이 배열을 선언하여 진행한다면 불필요한 코드를 줄일 수 있습니다.

 

2. 위의 주어진 경기를 진행할 수 있다면, 모두 진행하면서 주어진 결과의 승/무/패 에서 경기가 이루어진 것의 수를 1개씩 지워나갑니다. 

이를 통해 모든 연산 15번을 진행했다면 15번의 연산을 성공한것이므로 가능한 결과일 것 입니다.

이떄 각 결과가 적합하다면 15번의 모든 연산을 진행하므로 승/패, 무/무/, 패/승의 순서는 중요하지 않습니다.

 

이미 주어진 경기에서 그 경기를 진행할 수 있는 15번만큼 모두 지워나간다는 아이디어로 접근해야하는 문제였습니다.

 

처음에 백트래킹으로 6가지 팀이 나왔을떄 나올 수 있는 모든 경기의 수를 저장한뒤, 해당 경우의 수에 존재하는 결과라면 통과, 아니라면 비통과하는 방식도 떠올랐었지만, 구현하는 방법에 대해 감이 오지않아 주어진 경우의 수를 지우는 방안으로 선회했습니다.

 

헷갈렸었던점은.

//승패를 구분합니다.
if(arr[gameMatch1][0] > 0 && arr[gameMatch2][2] > 0) {
    arr[gameMatch1][0] -= 1;
    arr[gameMatch2][2] -= 1;
    simulate(level + 1);
    arr[gameMatch1][0] += 1;
    arr[gameMatch2][2] += 1;
}
 
if(arr[gameMatch1][1] > 0 && arr[gameMatch2][1] > 0) {
    arr[gameMatch1][1] -= 1;
    arr[gameMatch2][1] -= 1;
    simulate(level + 1);
    arr[gameMatch1][1] += 1;
    arr[gameMatch2][1] += 1;
}
 
if(arr[gameMatch1][2] > 0 && arr[gameMatch2][0] > 0) {
    arr[gameMatch1][2] -= 1;
    arr[gameMatch2][0] -= 1;
    simulate(level + 1);
    arr[gameMatch1][2] += 1;
    arr[gameMatch2][0] += 1;
}

이 부분에서 마지막 조건문입니다. gameMAtch1번팀의 패배 횟수와 gameMatch2번 팀의 승리횟수가 양수일경우 또한 고려해주어야합니다.

 

문제에서 각 경기의 조합을 구하고, 그 조합에서 어떤 나라가 먼저 이기고 지고 비기는지에 따라 경기 결과가 달라질 수 있습니다. 그러므로, 백트래킹을 활용하여 모든 경우에 대해서 성공하는 경우를 찾아야만 합니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
	public static int N, M;
	public static int[][] gameResult = new int[6][3]; //6팀의 승/무/패 3가지 경우의 수
	public static int[][] gameMatch = { {0,1}, {0, 2}, {0,3}, {0,4}, {0,5}, {1, 2}, {1, 3}, {1, 4}, {1, 5}, {2, 3}, {2, 4}, {2, 5}, {3, 4}, {3, 5}, {4, 5}};
	public static int answer = 0;
	public static boolean success = false, validInput = true;
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	for(int t=0; t<4; t++) {
    		StringTokenizer st = new StringTokenizer(br.readLine());
    		validInput = true;
    		success = false;
        	for(int i=0;i<6;i++) {
        		for(int j=0;j<3;j++) {
        			gameResult[i][j] = Integer.parseInt(st.nextToken());
        			if(gameResult[i][j] >= 6) { //만약 6 이상의 입력이 들어오면 경기횟수 초과.
        				validInput = false;
        			}
        		}
        	}
        	
        	simulate(0);
        	
        	if(success == true && validInput == true) {
        		System.out.print("1 ");
        	}else {
        		System.out.print("0 ");
        	}
    	}
    	
    	//경기 
    	
    }
	public static void simulate(int level) {
		if(success == true) {
			return ;
		}
		if(level == 15) { //15번 경기가 끝나면 총 30개의 승/무/패가 기록됩니다.
			success = true;
			return ;
		}
		
		int team1 = gameMatch[level][0];
		int team2 = gameMatch[level][1];
		
		//승 : 패 조사
		if( gameResult[team1][0] > 0 && gameResult[team2][2] > 0) {
			gameResult[team1][0] -= 1;
			gameResult[team2][2] -= 1;
			simulate(level + 1);
			gameResult[team1][0] += 1;
			gameResult[team2][2] += 1;
		}
		
		// 무 : 무 조사
		if( gameResult[team1][1] > 0 && gameResult[team2][1] > 0) {
			gameResult[team1][1] -= 1;
			gameResult[team2][1] -= 1;
			simulate(level + 1);
			gameResult[team1][1] += 1;
			gameResult[team2][1] += 1;
		}
		
		//패 : 승
		if( gameResult[team1][2] > 0 && gameResult[team2][0] > 0) {
			gameResult[team1][2] -= 1;
			gameResult[team2][0] -= 1;
			simulate(level + 1);
			gameResult[team1][2] += 1;
			gameResult[team2][0] += 1;
		}
		
	}
 
}

 

만약 참여팀이 6명이 아니라 100명이라면 조합을 직접 구해줍니다.

package Main;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;
public class Main {
	public static int N, M, K;
	public static boolean[] visited;
	public static LinkedList<int[]> combList = new LinkedList<>();
	public static Country[] country;
	public static int answer = 0;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//		StringTokenizer st = new StringTokenizer(br.readLine());
		
		/*
		(0, 1), (0, 2)(0, 3) (0, 4) (0, 5)
		(1, 2) (1, 3) (1, 4) (1, 5)
		(2, 3), (2, 4) (2, 5)
		(3, 4) (3, 5)
		(4, 5)
		*/
		
		country = new Country[6];
		visited = new boolean[6];
		makeComb(0, 0);
		
		for(int i=0;i<4;i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			answer = 0;
			boolean flag = true;
			
				
			for(int j=0;j<6;j++) {
				int inputWin = Integer.parseInt(st.nextToken());
				int inputDraw = Integer.parseInt(st.nextToken());
				int inputLose = Integer.parseInt(st.nextToken());
				country[j] = new Country(inputWin, inputDraw, inputLose);
				if(inputWin >= 6 || inputDraw >= 6 || inputLose >= 6) {
					flag = false;
				}
			}
			
			simulate(0);
			
			if(flag == true && answer == 1)
				System.out.println(answer);
			else
				System.out.println(0);
			
		}
		
	}
	
	public static void makeComb(int level, int countryIdx) {
		if(level == 2) {
			int firstCountry = -1, secondCountry = -1;
			for(int i=0;i<6;i++) {
				if(visited[i] == true) {
					if(firstCountry == -1) {
						firstCountry = i;
					}else if(firstCountry != -1) {
						secondCountry = i;
					}
				}
			}
			combList.add(new int[] {firstCountry, secondCountry});
			return ;
		}
		
		for(int i=countryIdx; i<6;i++) {
			visited[i] = true;
			makeComb(level + 1, i + 1);
			visited[i] = false;	
		}
		
	}
 
	public static void simulate(int level) {
		if(level >=15) {
			answer = 1;
			return ;
		}
		
		int firstCountry = combList.get(level)[0];
		int secondCountry = combList.get(level)[1];
		
		if( country[firstCountry].win > 0 && country[secondCountry].lose > 0) {
			country[firstCountry].win -= 1;
			country[secondCountry].lose -= 1;
			simulate(level + 1);
			country[firstCountry].win += 1;
			country[secondCountry].lose += 1;
		} 
		if(country[firstCountry].draw > 0 && country[secondCountry].draw > 0) {
			country[firstCountry].draw -= 1;
			country[secondCountry].draw -= 1;
			simulate(level + 1);
			country[firstCountry].draw += 1;
			country[secondCountry].draw += 1;
		} 
		if(country[firstCountry].lose > 0 && country[secondCountry].win > 0) {
			country[firstCountry].lose -= 1;
			country[secondCountry].win -= 1;
			simulate(level + 1);
			country[firstCountry].lose += 1;
			country[secondCountry].win += 1;
		}
		
	}
}
 
class Country{
	int win;
	int draw;
	int lose;
	public Country(int win, int draw, int lose) {
		this.win = win;
		this.draw = draw;
		this.lose = lose;
	}
}

 

경기 순서를 미리 정하지 않고, 완전탐색을 할경우 시간초과가 발생합니다.

6개의 나라가 존재한다면 6 * 5 / 2 로 15가지의 경기에 대한 완전탐색을 진행하면 되는데 만약에 그렇지않다면 모든경우를 탐색해야 합니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
	public static int N, M;
	public static Country[] country = new Country[6];
	public static int answer = 0;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//		StringTokenizer st = new StringTokenizer(br.readLine());
		
//		N = Integer.parseInt(st.nextToken());
		for(int i=0;i<4;i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int j=0;j<6;j++) {
				int inputWin = Integer.parseInt(st.nextToken());
				int inputDraw = Integer.parseInt(st.nextToken());
				int inputLose = Integer.parseInt(st.nextToken());
				
				country[j] = new Country(inputWin, inputDraw, inputLose);
			}
			answer = 0;
			simulate(0, 0, 0);
			
			System.out.println(answer);
		}
	}
	
	public static void simulate(int level, int countryIdx, int gameCount) {
		if( countryIdx >= 6 ) {
			if(gameCount == 15) {
				answer = 1;	
			}
			return ;
		}
		
		if(country[countryIdx].win > 0) {
			for(int i=countryIdx + 1; i < 6;i++) {
				if(country[i].lose > 0) {
					country[countryIdx].win -= 1;
					country[i].lose -= 1;
					simulate(level + 1, countryIdx, gameCount + 1);	
					country[countryIdx].win += 1;
					country[i].lose += 1;
				}
			}	
		}
		
		if(country[countryIdx].draw > 0) {
			for(int i=countryIdx + 1; i < 6;i++) {
				if(country[i].draw > 0) {
					country[countryIdx].draw -= 1;
					country[i].draw -= 1;
					simulate(level + 1, countryIdx, gameCount + 1);
					country[countryIdx].draw += 1;
					country[i].draw += 1;
				}
			}	
		}
		
		if(country[countryIdx].lose > 0) {
			for(int i=countryIdx + 1; i < 6;i++) {
				if(country[i].win > 0) {
					country[countryIdx].lose -= 1;
					country[i].win -= 1;
					simulate(level + 1, countryIdx, gameCount + 1);
					country[countryIdx].lose += 1;
					country[i].win += 1;
				}
			}	
		}
		
		simulate(level + 1, countryIdx + 1, gameCount);
		
	}
	
}
 
class Country{
	int win;
	int draw;
	int lose;
	public Country(int win, int draw, int lose) {
		this.win = win;
		this.draw = draw;
		this.lose = lose;
	}
}