월드컵
문제
월드컵 조별 최종 예선에서는 6개국으로 구성된 각 조별로 동일한 조에 소속된 국가들과 한 번씩, 각 국가별로 총 5번의 경기를 치른다. 조별리그가 끝난 후, 기자가 보내온 각 나라의 승, 무승부, 패의 수가 가능한 결과인지를 판별하려고 한다. 다음은 가능한 결과와 가능하지 않은 결과의 예이다.
나라 승 무 패
A 5 0 0
B 3 0 2
C 2 0 3
D 0 0 5
E 4 0 1
F 1 0 4
나라 승 무 패
A 4 1 0
B 3 0 2
C 4 1 0
D 1 1 3
E 0 0 5
F 1 1 3
나라 승 무 패
A 5 0 0
B 4 0 1
C 2 2 1
D 2 0 3
E 1 0 4
F 0 0 5
나라 승 무 패
A 5 0 0
B 3 1 1
C 2 1 1
D 2 0 3
E 0 0 5
F 1 0 4
예제 1 가능한 결과 예제 2 가능한 결과 예제 3 불가능한 결과 예제 4 불가능한 결과
네 가지의 결과가 주어질 때 각각의 결과에 대하여 가능하면 1, 불가능하면 0을 출력하는 프로그램을 작성하시오.
입력
첫째 줄부터 넷째 줄까지 각 줄마다 6개국의 결과가 나라별로 승, 무승부, 패의 순서로 빈칸을 하나 사이에 두고 18개의 숫자로 주어진다. 승, 무, 패의 수는 6보다 작거나 같은 자연수 또는 0이다.
출력
입력에서 주어진 네 가지 결과에 대하여 가능한 결과는 1, 불가능한 결과는 0을 빈칸을 하나 사이에 두고 출력한다.
풀이
경기는 모든 팀이 서로 한경기씩 진행한다.
주의할 점은 A-B 경기를 하면 B-A경기는 동일하기 때문에 한번 더 진행하지 않아도 된다.
즉 총 경기는
A : B C D E F
B : C D E F
C : D E F
.
.
.
F : G
총 15개의 경기가 이루어진다.
경기를 진행하는 경우의 수를 미리 저장해두고 ex) 배열 두개를 사용 int[] t1, int[] t2
경기를 하나씩 진행하며 할 수 있는 모든 경우의 수를 확인한다.
주의할 점은 경기의 승,패를 진행할 때 해당 팀에 남아있는 승리 수 or 패배 수가 존재해야 한다.
하나씩 대입하여 백트레킹을 진행했을 때 15번째 경기까지 완료가 된다면 가능한 결과이다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main{
static int[] t1;
static int[] t2;
static int[] win;
static int[] draw;
static int[] lose;
static boolean isOk;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int cnt = 0;
t1 = new int[15];
t2 = new int[15];
for(int i=0;i<5;i++) {
for(int j=i+1;j<6;j++) {
t1[cnt]=i;
t2[cnt++]=j;
}
}
String ans = "";
win = new int[6];
draw = new int[6];
lose = new int[6];
for (int i = 0; i < 4; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int total = 0;
for (int j = 0; j < 6; j++) {
total += win[j] = Integer.parseInt(st.nextToken());
total += draw[j] = Integer.parseInt(st.nextToken());
total += lose[j] = Integer.parseInt(st.nextToken());
}
isOk = false;
if(total == 30)
backTracking(0);
if (isOk) {
ans += "1 ";
} else {
ans += "0 ";
}
}
System.out.println(ans.trim());
}
static void backTracking(int depth) {
if (isOk) {
return;
}
if (depth == 15) {
isOk = true;
return;
}
int a = t1[depth];
int b = t2[depth];
//t1 win
if (win[a] > 0 && lose[b] > 0) {
win[a]--;
lose[b]--;
backTracking(depth + 1);
win[a]++;
lose[b]++;
}
// draw
if (draw[a] > 0 && draw[b] > 0) {
draw[a]--;
draw[b]--;
backTracking(depth + 1);
draw[a]++;
draw[b]++;
}
//t1 lose
if (lose[a] > 0 && win[b] > 0) {
lose[a]--;
win[b]--;
backTracking(depth + 1);
lose[a]++;
win[b]++;
}
}
}
'알고리즘' 카테고리의 다른 글
1080 행렬 (Java) (0) | 2022.04.23 |
---|---|
3020 개똥벌레 (Java) (0) | 2022.04.22 |
1068 트리 (Java) (0) | 2022.04.19 |
1034 램프 (Java) (0) | 2022.04.18 |
1052 물병 (Java) (0) | 2022.04.18 |