[백준 / Java] 6987번: 월드컵 (골드4)

문제 풀이 날짜: 2023.08.16
포스트 작성일: 2023.08.16

 

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

 

문제 출처

백준 온라인 저지 6987번: 월드컵 (골드4)

 

키워드

백트랙킹, 상태 탐색

 

풀이 접근법

• 단순히 이긴 횟수, 비긴 횟수, 패배한 횟수만을 비교해서 답을 구할 수 없다.
• 예를 들면 '5 0 0 5 0 0 5 0 0 0 0 5 0 0 5 0 0 5' 과 같은 경우 승패가 짝이 맞지만, 한 팀이 5승을 하기 위해서는 다른 팀 전적에 최소 1패 씩은 있어야 한다.
• 따라서 해당 문제를 풀기 위해선 각 팀별로 모두 최소 1번씩 승리 - 무승부 - 패배를 체크하며 풀이해야 한다.
  • 1 → 2, 3, 4, 5, 6
  • 2 → 3, 4, 5, 6
  • 3 → 4, 5, 6
  • 4 → 5, 6
  • 5 → 6
• 재귀를 승리 - 무승부 - 패배의 세 갈래로 호출시킨다. (자식이 3개인 상태 탐색 트리 형태)  
• 만약 '5 0 0 3 0 2 2 0 3 0 0 5 4 0 1 1 0 4' 이라는 입력이 있을 때…
  • 모든 경기의 승패를 따지면서 입력 값을 감소시켜 '0 0 0 0 0 0 0 0 0 ...' 으로 만들어보자.
  • 만약 경기 횟수를 감소시키다가 음수값이나온다면 불가능한 경우의 수이다. (승-패 짝이 맞지 않음)
  • 백트래킹을 완료했을 때 모두 0으로 채워진 결과물을 얻게 된다면 가능한 경우의 수 이다.
• 대진표(games 리스트)를 미리 생성하여 참조하면 보다 쉽게 풀 수 있다.

 

코드

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

public class Main {

	private static final int TEAM = 6;
	private static final int COUNT = 3;

	private static final int WIN = 0;
	private static final int DRAW = 1;
	private static final int LOSE = 2;

	private static final int MATCH_COUNT = 15;
	
	private static int result;
	private static List<String> games;

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

		StringBuilder sb = new StringBuilder();
		for (int tc = 0; tc < 4; tc++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");

			//games에 대결 정보를 미리 생성한다.
			games = new ArrayList<>();
			
			for(int i = 0; i < TEAM; i++) {
				for(int j = i + 1; j < TEAM; j++) {
					games.add(i + "" + j);
				}
			}
			
			int[][] matches = new int[TEAM][COUNT];
			for (int i = 0; i < TEAM; i++) {
				for (int j = 0; j < COUNT; j++) {
					matches[i][j] = Integer.parseInt(st.nextToken());
				}
			}

			result = 0;
			backTracking(matches, 0);

			sb.append(result).append(" ");
		}

		System.out.println(sb);
	}

	private static void backTracking(int[][] matches, int depth) {
		if (MATCH_COUNT == depth) {
			if(!isValidResult(matches)) {
				return;
			}
			result = 1;
			return;
		}
		
		int curr = games.get(depth).charAt(0) - '0';
		int rival = games.get(depth).charAt(1) - '0';

		// 승부 결과 생성
		if(matches[curr][WIN] > 0 && matches[rival][LOSE] > 0) {
			// 1.승 & 패
			matches[curr][WIN]--;
			matches[rival][LOSE]--;
			backTracking(matches, depth + 1);
			matches[curr][WIN]++;
			matches[rival][LOSE]++;
		}

		if(matches[curr][DRAW] > 0 && matches[rival][DRAW] > 0) {
			// 2.무 & 무
			matches[curr][DRAW]--;
			matches[rival][DRAW]--;
			backTracking(matches, depth + 1);
			matches[curr][DRAW]++;
			matches[rival][DRAW]++;
		}

		if(matches[curr][LOSE] > 0 && matches[rival][WIN] > 0) {
			// 3.패 & 승
			matches[curr][LOSE]--;
			matches[rival][WIN]--;
			backTracking(matches, depth + 1);
			matches[curr][LOSE]++;
			matches[rival][WIN]++;
		}

		return;
	}

	private static boolean isValidResult(int[][] matches) {
		for (int i = 0; i < TEAM; i++) {
			for (int j = 0; j < COUNT; j++) {
				if(matches[i][j] != 0) return false;
			}
		}
		
		return true;
	}

}

---

어느 것을 백트랙킹으로 구하고 원복시킬지 정하기 어려운 문제였다. 처음에는 가능한 모든 승패횟수를 구해서 입력과 같은 것이 발견되면 그것을 답으로 삼으려고 했으나, 역으로 생각하여 입력 배열을 모두 0으로 만드는 것이 비교적 쉬운 접근법이었다. 풀이가 쉽게 구상되지 않아 다른 블로그를 참고하여 풀이했다.

 

참고한 링크

https://maivve.tistory.com/215

https://dkswnkk.tistory.com/653

 

git 링크

(git 링크 첨부)