[Algorithm] 6987 - 월드컵

목차

---

1. 문제 설명

2. 접근 방식

3. 코드

 

 

 

 

 

1. 문제 설명

---

 

 

승패를 기록한 결과를 보고 가능한 결과인지, 불가능한 결과인지를 검사하는 문제다. 

이때 가능한 결과라면 "1"을 출력하고, 불가능한 결과라면 "0"을 출력한다. 

 

 

2. 접근 방식

---

조별 예선은 총 6개의 국가가 같은 조에 속한 국가들과 한 번씩 경기를 치룬다. 

⭐⭐⭐ 즉, 총 경기 횟수는 6C2로 15개가 된다. ⭐⭐⭐

 

이때 15개의 가능한 경기쌍을 구하고 해당 경기에 대해 승, 무, 패 결과를 백트래킹한다면

모든 경기를 순회했을 때 입력받은 예제의 가능 여부를 판별할 수 있다. 

 

이를 코드로 구현해보자. 

 

 

3. 코드

---

import java.io.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {
    public static List<int[]> matches;
    public static boolean possible;

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

        // 가능한 경기쌍 만들기
        matches = new ArrayList<>();
        for(int i = 0; i < 6; i++) {
            for(int j = i + 1; j < 6; j++) {
                matches.add(new int[]{ i, j });
            }
        }

        for(int i = 0; i < 4; i++) {
            int[][] result = new int[6][3];
            int[] info = Arrays.stream(br.readLine().split(" "))
                    .mapToInt(Integer::parseInt)
                    .toArray();

            int index = 0;
            for (int j = 0; j < 6; j++) {
                for (int k = 0; k < 3; k++) result[j][k] = info[index++];
            }

            possible = false;
            dfs(0, result);

            if(possible) System.out.print("1 ");
            else System.out.print("0 ");
        }
    }

    public static void dfs(int round, int[][] result) {
        if(possible) return;

        if(round == 15) {
            for(int i = 0; i < 6; i++) {
                for(int j = 0; j < 3; j++) {
                    if(result[i][j] != 0) possible = false;
                }
            }
            possible = true;
            return;
        }

        int[] match = matches.get(round);
        int a = match[0];
        int b = match[1];

        // 1. a 승, b 패
        if(result[a][0] > 0 && result[b][2] > 0) {
            result[a][0]--; result[b][2]--;
            dfs(round + 1, result);
            result[a][0]++; result[b][2]++;
        }

        // 2. a 패, b 승
        if(result[a][2] > 0 && result[b][0] > 0) {
            result[a][2]--; result[b][0]--;
            dfs(round + 1, result);
            result[a][2]++; result[b][0]++;
        }

        // 3. a 무, b 무
        if(result[a][1] > 0 && result[b][1] > 0) {
            result[a][1]--; result[b][1]--;
            dfs(round + 1, result);
            result[a][1]++; result[b][1]++;
        }
    }
}

 

 

먼저 가능한 경기쌍을 구한다. (총 15개로 고정)

matches = new ArrayList<>();
for(int i = 0; i < 6; i++) {
    for(int j = i + 1; j < 6; j++) {
        matches.add(new int[]{ i, j });
    }
}

 

(A, B) = (B, A)로 각 국가들은 한 번씩만 경기를 치룬다. 

중복되는 경우의 수가 발생하지 않도록 경기쌍 (i, j)를 구한다. 

 

for(int i = 0; i < 4; i++) {
    int[][] result = new int[6][3];
    int[] info = Arrays.stream(br.readLine().split(" "))
            .mapToInt(Integer::parseInt)
            .toArray();

    int index = 0;
    for (int j = 0; j < 6; j++) {
        for (int k = 0; k < 3; k++) result[j][k] = info[index++];
    }

    possible = false;
    dfs(0, result);

    if(possible) System.out.print("1 ");
    else System.out.print("0 ");
}

 

입력받은 예제를 result[6][3]에 저장한다.

국가는 총 6개, 승무패 3가지 결과를 저장하기 때문에 6 * 3으로 생성해준다. 

dfs 메소드로는 경기 결과를 백트래킹해가면 가능 여부를 검사한다. 

 

int[] match = matches.get(round);
int a = match[0];
int b = match[1];

// 1. a 승, b 패
if(result[a][0] > 0 && result[b][2] > 0) {
    result[a][0]--; result[b][2]--;
    dfs(round + 1, result);
    result[a][0]++; result[b][2]++;
}

// 2. a 패, b 승
if(result[a][2] > 0 && result[b][0] > 0) {
    result[a][2]--; result[b][0]--;
    dfs(round + 1, result);
    result[a][2]++; result[b][0]++;
}

// 3. a 무, b 무
if(result[a][1] > 0 && result[b][1] > 0) {
    result[a][1]--; result[b][1]--;
    dfs(round + 1, result);
    result[a][1]++; result[b][1]++;
}

 

dfs의 일부다. 

먼저 matches에서 검사할 경기쌍에서 국가 A, B를 구한다. 

• A 승 / B 패
• A 패 / B 승
• A 무 / B 무

총 3가지 경우의 수가 가능하다.

 

각각의 경우의 수에 대해 result값을 감소시킨채로 다음 경기 결과를 구하고 (dfs 호출)

현재 결과는 원복시켜준다. → 백트래킹 기본 원칙

 

이때 result는 남아있는 승부의 개수로 생각했다. 

만약 result값이 0보다 작다면 남아있는 승부가 없다는 뜻으로, 모든 경기를 검사한 뒤에는 

if(possible) return;

if(round == 15) {
    for(int i = 0; i < 6; i++) {
        for(int j = 0; j < 3; j++) {
            if(result[i][j] != 0) possible = false;
        }
    }
    possible = true;
    return;
}

 

result가 0인지 검사한다. 

백트래킹 전에 경기쌍의 결과만큼 감소시켜줬기 때문에 result가 0이 아니라면 경기가 남아있다는 뜻이며

이는 곧 불가능한 결과임을 의미한다. 

 

가능한 결과라면 더 이상 dfs로 검사할 필요가 없다. 

그래서 possible을 전역변수로 만들고, true일 땐 dfs 자체를 탈출할 수 있도록 처리해주었다.