[백준] 알고리즘 분류(백트래킹,JAVA)6987번, 월드컵

문제 링크

6987번: 월드컵

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 6개국으로 구성된 조는 다른 국가와 한 번씩 총 5번의 경기를 진행합니다.

2. 4개의 결과가 주어질 때 가능한 결과는 1, 불가능한 결과는 0으로 출력합니다.

3. 승, 무, 패는 6보다 작거나 같은 자연수 또는 0입니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 각 조별에 대해서 경기가 원할하게 진행되는지 백트래킹 탐색을 진행합니다.

 

3. 탐색이 종료한 뒤, 각 조별 결과가 가능하면 1, 불가능하면 0을 결과로 출력합니다.

 

백트래킹 탐색!

 

각 나라가 다른 나라와 경기에서 발생할 수 있는 경우의 수

 

1. 승리

: ( 현재 팀 승 > 0 && 상대 팀 패 > 0)

 

2. 무승부

: ( 현재 팀 무 > 0 && 상대 팀 무 > 0)

 

3. 패배

: ( 현재 팀 패 > 0 && 상대 팀 승 > 0)

 

 

탐색을 진행할 때

 

A 국가 : B, C, D, E, F

 

B 국가 : C, D, E, F

 

C 국가 : D, E, F

...

 

경기를 비교하여 경기에서 발생하는 모든 경우의 수가 국가 F까지 도달하면 해당 결과는 올바른 것입니다.

 

 

예제입력 1.

 

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

 

 

2. 각 조별에 대해서 경기가 원할하게 진행되는지 백트래킹 탐색을 진행합니다.

 

A국가 탐색!

 

A - B : 승리

 

A - C : 승리

 

A - D : 승리

 

A - E : 승리

 

A - F : 승리

B국가 탐색

 

B - C : 승리

B - D : 승리

B - E : 패배

B - F : 승리

 

C국가 탐색

C - D : 승리

C - E : 패배

C - F : 승리

D국가  탐색

 

D - E : 패배

D - F : 패배

D국가  탐색

 

E - F : 승리

올바른 결과 확인!

 

3. 탐색이 종료한 뒤, 각 조별 결과가 가능하면 1, 불가능하면 0을 결과로 출력합니다.

 

탐색했을 때 가능한 경우가 존재하므로

1 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여 경기의 결과 정보들을 띄어쓰기 기준 나누었습니다.
• 각 국가의 경기 결과가 5개가 아니면 올바르지 못한 결과인 것을 확인합니다.
• search함수를 실행하여 모든 경기가 올바르게 진행되는지 탐색합니다.
• 탐색이 끝난 뒤 올바른 결과의 경우가 존재하면 1, 아니면 0을 결과로 StringBuilder에 저장하였습니다.
• System.out.print()으로 StringBuilder에 저장된 결과값을 출력하였습니다.

• search함수는 국가와 경기를 진행하는 3가지 경우로 탐색을 진행합니다.
• search함수는 F국가까지 경기를 올바르게 완료하면 올바른 결과로 판정합니다.

 

결과코드

 

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

public class BOJ6987 {
    static int[][] play = new int[6][3];	//경기 결과 저장 배열
    static int answer = 0;

    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        //4개의 일정 탐색 진행
        for (int i = 0; i < 4; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            answer = 0;
            //경기 정보 저장
            for (int j = 0; j < 18; j++)
                play[j / 3][j % 3] = Integer.parseInt(st.nextToken());
            boolean flag = false;
            //경기 수가 5가 아닌 국가가 있을 경우 올바른 결과 절대 불가능!
            for(int j=0;j<6;j++) {
                if(play[j][0] + play[j][1] + play[j][2] != 5) {
                    flag = true;
                    break;
                }
            }
            if(!flag)	//모든 국가의 경기수가 5일 때 백트래킹 탐색 진행
                search(0, 1);
            sb.append(answer).append(" ");
        }
        System.out.print(sb);	//결과 출력
    }

    //국가별 경기를 경우를 탐색하는 백트래킹 함수
    private static void search(int idx, int nxt) {
        if (answer == 1)	//해당 결과가 올바른 것일 때 재귀 종료!
            return;
        //F국가까지 올바르게 경기가 진행되었을 때
        if (idx == 5) {
            answer = 1;
            return;
        }
        //현재 국가가 상대 국가에게 이겼을 때
        if (play[idx][0] > 0 && play[nxt][2] > 0) {
            play[idx][0]--;
            play[nxt][2]--;
            if (nxt == 5) {	//현재 국가 탐색 완료
                search(idx + 1, idx + 2);
            }else
                search(idx, nxt + 1);
            play[idx][0]++;
            play[nxt][2]++;
        }
        //현재 국가와 상대 국가가 무승부 했을 때
        if (play[idx][1] > 0 && play[nxt][1] > 0) {
            play[idx][1]--;
            play[nxt][1]--;
            if (nxt == 5) {	//현재 국가 탐색 완료
                search(idx + 1, idx + 2);
            }else
                search(idx, nxt + 1);
            play[idx][1]++;
            play[nxt][1]++;
        }
        //현재 국가가 상대 국가에게 패배하였을 때
        if (play[idx][2] > 0 && play[nxt][0] > 0) {
            play[idx][2]--;
            play[nxt][0]--;
            if (nxt == 5) {	//현재 국가 탐색 완료
                search(idx + 1, idx + 2);
            }else
                search(idx, nxt + 1);
            play[idx][2]++;
            play[nxt][0]++;
        }

    }
}