목차
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 자체를 탈출할 수 있도록 처리해주었다.
'Problem Solving > BOJ' 카테고리의 다른 글
| [Algorithm] 1027 - 고층 건물 (0) | 2025.09.22 |
|---|---|
| [Algorithm] 5052 - 전화번호 목록 (0) | 2025.09.08 |
| [Algorithm] 1197 - 최소 스패닝 트리 (0) | 2025.09.03 |
| [Algorithm] 1138 - 한 줄로 서기 (1) | 2025.09.01 |
| [Algorithm] 12865 - 평범한 배낭 (1) | 2025.03.17 |