[swea] 규영이와 인영이의 카드게임

Об этом предложении

문제 링크 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWgv9va6HnkDFAW0 1. 문제 접근 이 문제에서 가장 먼저 파악해야 하는 것은 어떤 값이 고정 되어 있고, 어떤 값이 변하는가 이다. 규영 이가 내는 9장의 카드 순서는 입력으로 주어져 고정 되어 있다. 반면 인영 이는 규영이가 가지지 않은 나머지 9장의 카드를 가지고 있으며, 이 카드들을 내는 순서 에 따라 경기 결과가 달라진다. 예를 들어 인영이의 카드가 3장이라고 단순화하면, [2, 4, 6] 가능한 순서 2 4 6 2 6 4 4 2 6 4 6 2 6 2 4 6 4 2 같은 카드를 사용하더라도 순서 가 달라지면 서로 다른 경우가 된다. 따라서 인영이가 카드를 내는 모든 순서를 만들어 확인해야 한다. 9개의 카드를 순서를 고려 하여 나열한다 → 순열 인영이 카드의 모든 순열은 9! = 362,880 개이므로 완전탐색 으로 확인할 수 있다. 2. 전체 풀이 흐름 문제를 크게 나누면 다음과 같다. 규영이 카드 9장 입력 ↓ 규영이가 가지지 않은 카드 = 인영이 카드 9장 구하기 ↓ DFS로 인영이 카드의 모든 순열 생성 ↓ 9장의 순서가 완성되면 규영이와 인영이 카드 비교 ↓ 9라운드의 점수 계산 ↓ 규영이 승 / 패 횟수 증가 핵심은 인영이 카드의 모든 순서를 DFS로 만드는 것이다. 3. 순열에서 depth와 i 순열을 구현할 때 가장 헷갈렸던 부분은 depth 와 반복문의 i 가 각각 무엇을 의미하는가였다. static void dfs(int depth) { for (int i = 0; i < 9; i++) { if (visited[i]) continue; visited[i] = true; selected[depth] = inYoung[i]; dfs(depth + 1); visited[i] = false; } } 각 변수의 역할은 다음과 같이 생각할 수 있다. depth = 현재 몇 번째 자리를 결정하고 있는가? i = 현재 자리에 어떤 카드를 넣을 것인가? 예를 들어 인영이의 카드가 다음과 같다고 하자. inYoung = [2, 4, 6] depth = 0 이면 첫 번째 자리를 결정하고 있는 것이다. i = 0 → selected[0] = 2 i = 1 → selected[0] = 4 i = 2 → selected[0] = 6 반복문의 i 를 통해 현재 자리에 들어갈 수 있는 모든 카드를 하나씩 선택한다. 4. visited가 필요한 이유 순열 에서는 하나의 카드를 한 번만 사용할 수 있다. 따라서 이미 선택한 카드인지 확인하기 위해 visited 배열을 사용한다. if (visited[i]) continue; 아직 사용하지 않은 카드라면 선택한다. visited[i] = true; selected[depth] = inYoung[i]; 그리고 다음 자리를 결정한다. dfs(depth + 1); 해당 카드를 선택했을 때 발생하는 모든 경우를 확인했다면 다시 사용하지 않은 상태로 되돌린다. visited[i] = false; 전체 흐름은 다음과 같다. 카드 선택 ↓ visited = true ↓ selected[depth]에 저장 ↓ dfs(depth + 1) ↓ visited = false ↓ 다른 카드 선택 이것이 백트래킹의 선택 → 재귀 → 원상복구 구조이다. 5. DFS가 실제로 동작하는 과정 카드가 3장이라고 가정해보자. [2, 4, 6] DFS는 다음과 같이 진행된다. depth = 0 ├── 2 선택 │ │ │ ├── 4 선택 │ │ └── 6 선택 │ │ → [2, 4, 6] │ │ │ └── 6 선택 │ └── 4 선택 │ → [2, 6, 4] │ ├── 4 선택 │ │ │ ├── 2 선택 │ │ └── 6 선택 │ │ → [4, 2, 6] │ │ │ └── 6 선택 │ └── 2 선택 │ → [4, 6, 2] │ └── 6 선택 │ ├── 2 선택 │ └── 4 선택 │ → [6, 2, 4] │ └── 4 선택 └── 2 선택 → [6, 4, 2] 3장의 카드라면 3! = 6개의 순열이 만들어진다. 실제 문제에서는 9장의 카드이므로 9! = 362,880 개의 순열을 탐색한다. 6. 순열이 완성되었는지 확인 depth == 9 가 되었다는 것은 selected[0] ~ selected[8] 까지 모두 채워졌다는 의미이다. 즉, 인영이가 카드를 내는 하나의 순서가 완성된 것이다. if (depth == 9) { // 점수 계산 return; } 예를 들어 selected = [2, 6, 4, 10, 12, 15, 18, 7, 3] 처럼 하나의 순열이 완성되었다면 이제 규영이의 카드와 라운드별로 비교한다. 7. 점수 계산 각 라운드에서는 두 사람이 낸 카드의 숫자를 비교한다. 숫자가 더 큰 사람이 두 카드에 적힌 숫자의 합만큼 점수를 얻는다. int gyuScore = 0; int inScore = 0; for (int i = 0; i < 9; i++) { int sum = gyuYoung[i] + selected[i]; if (gyuYoung[i] > selected[i]) { gyuScore += sum; } else { inScore += sum; } } 9라운드가 끝난 후 최종 점수를 비교한다. if (gyuScore > inScore) { win++; } else { lose++; } 이 과정을 인영이가 카드를 낼 수 있는 모든 순서에 대해 반복한다. 8. 핵심 DFS 구조 결국 이 문제의 핵심 코드는 다음과 같은 순열 구조 이다. static void dfs(int depth) { if (depth == 9) { int gyuScore = 0; int inScore = 0; for (int i = 0; i < 9; i++) { int sum = gyuYoung[i] + selected[i]; if (gyuYoung[i] > selected[i]) { gyuScore += sum; } else { inScore += sum; } } if (gyuScore > inScore) { win++; } else { lose++; } return; } for (int i = 0; i < 9; i++) { if (visited[i]) continue; visited[i] = true; selected[depth] = inYoung[i]; dfs(depth + 1); visited[i] = false; } } 이 코드를 순열의 관점에서 다시 보면 dfs(depth) 1. depth == 9 → 순열 하나 완성 → 경기 결과 계산 2. 아직 완성되지 않았다면 for (모든 카드 후보 i) 이미 사용했으면 continue 카드 선택 visited[i] = true 현재 자리에 카드 저장 selected[depth] = inYoung[i] 다음 자리 결정 dfs(depth + 1) 원상복구 visited[i] = false 가 된다. 9. 시간복잡도 인영이 카드 9장의 모든 순열을 확인한다 (9!) 그리고 하나의 순열이 완성될 때마다 최대 9번의 카드 비교를 수행한다. 따라서 시간복잡도는 O(9! × 9) 이다. 9! = 362,880 이므로 완전탐색으로 충분히 해결할 수 있다. 10. 이 문제에서 배운 점 처음에는 카드게임의 승패를 계산하는 것에 집중해서 순열 문제라는 것을 바로 파악하기 어려웠다. 하지만 문제에서 고정된 것과 변하는 것을 구분해보니 규영이의 카드 순서는 고정되어 있고, 인영이가 카드를 내는 순서가 계속 달라진다는 것을 확인할 수 있었다. 따라서 인영이의 9장의 카드를 순서를 고려하여 나열하는 순열 문제로 접근할 수 있었다. 또한 순열 DFS에서 사용되는 변수의 역할을 다음과 같이 정리할 수 있었다. depth → 현재 결정할 자리 i → 현재 자리에 넣을 후보 visited → 이미 사용한 후보인지 확인 selected → 현재까지 만든 순열 특히 DFS 코드를 단순히 암기하기보다 선택 → 재귀 → 원상복구 → 다른 선택 이라는 흐름으로 이해하는 것이 중요하다는 것을 배웠다. 앞으로 문제에서 “N개의 원소를 순서를 고려하여 배치하고 모든 경우를 확인해야 한다” 는 특징이 보이면 순열과 백트래킹을 먼저 생각해볼 수 있을 것 같다. 전체 구현 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; // 규영이와 인영이 public class Solution { static int guWin, guLose; static int[] guCard; static int[] inCard; static boolean[] visited; static int[] selected; static void dfs(int depth, int guScore, int inScore){ // depth == 9 일때 점수 계산 if(depth == 9){ if(guScore>inScore){ guWin++; }else{ guLose++; } return; } // 인영 카드 순열 for(int i=0; i<9; i++){ if(visited[i]) continue; visited[i] = true; selected[depth] = inCard[i]; int sum = selected[depth] + guCard[depth]; if(selected[depth] > guCard[depth]){ dfs(depth+1, guScore, inScore+sum); }else{ dfs(depth+1, guScore+sum, inScore); } visited[i] = false; } } public static void main(String[] args) throws IOException { // 규영이가 이기는 경우와 지는 경우 BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int T = Integer.parseInt(br.readLine()); for(int tc=1; tc<=T; tc++){ StringTokenizer st = new StringTokenizer(br.readLine()); guCard = new int[9]; inCard = new int[9]; boolean[] cardSelected = new boolean[19]; // 규영이 카드 입력 for(int i=0; i<9; i++){ guCard[i] = Integer.parseInt(st.nextToken()); cardSelected[guCard[i]] = true; } // 인영이 카드 입력 int idx = 0; for(int i=1; i<=18; i++){ if(cardSelected[i]) continue; inCard[idx++] = i; } guLose = 0; guWin = 0; visited = new boolean[9]; selected = new int[9]; // dfs (깊이, 규영이 점수, 인영이 점수) dfs(0, 0, 0); System.out.println("#"+tc+" "+guWin+ " "+guLose); } } }