백준 23749번 : 카드컨트롤
이번 문제는 A와 B가 있을 때, A만 카드를 한 번에 하나를 빼내서 카드의 제일 위에 올리는 동작을 할 수 있고, 이 경우 A가 최소한의 조작으로 B를 이길 수 있을 때 몇 번의 조작을 해야하는지를 리턴하는 문제이다.
카드는 O가 적힌 카드 N장, X가 적힌 카드 N장이 주어지며 서로 다른 카드일 때 O 카드를 들고 있는 사람이 1점을 얻는다.
만약 같은 카드라면 무승부이기 때문에 점수가 없다.
결국 게임 시작 전 조작을 몇번 해야 이길 수 있는지를 리턴하는 문제이기 때문에 분기를 나누어 실행하면 된다.
이 문제는 박카스러버 블로그를 참고했다.
거의 동일한 로직으로 보면서 쓰면서 이해하는 시간을 가졌는데, 문제가 간단해 보이지만 생각보다 어떻게 동작을 나눠야할지 알기 어려웠다.
우선 메인 함수부터 살펴본다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Main {
public static void main(String[] args) throws java.io.IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int n = Integer.parseInt(br.readLine());
st = new StringTokenizer(br.readLine());
boolean[] isO = new boolean[2 * n];
for (int i = 0; i < 2 * n; i++) {
if (st.nextToken().charAt(0) == 'O') {
isO[i] = true;
}
}
int result = bfs(isO, 2 * n);
System.out.println(result);
}
입력에 대한 부분은 지나가고, 받은 입력을 바탕으로 boolean 타입 배열 isO를 생성하고, 각 카드가 O인지 X인지에 따라 true 혹은 false로 배열을 채운다.
다음으로 bfs 함수는
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public static int bfs(boolean[] isO, int n) {
int count = 0;
Queue<boolean[]> q = new LinkedList<>();
q.offer(isO);
Set<String> visited = new HashSet<>();
while (!q.isEmpty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
boolean[] cur = q.poll();
if (isWin(cur, n)) {
return count;
}
for (int j = 0; j < n; j++) {
boolean[] nxt = change(j, cur, n);
if (!visited.contains(Arrays.toString(nxt))) {
q.offer(nxt);
visited.add(Arrays.toString(nxt));
}
}
}
count++;
}
return -1;
}
최소 조작 횟수를 찾기 위해 작성되었다.
큐를 활용하여 탐색해야할 카드 배열의 상태를 유지하고 set 자료구조로 사용된 visited는 카드 배열 상태를 기록하기 위해 구현되었다.
큐에서 상태를 하나씩 꺼내, isWin 메서드를 활용하여 승리 조건을 만족하는지 확인한다.
만약 승리 조건을 만족하게 되면 현재까지의 조작 횟수인 count를 반환한다.
반대로 승리 조건을 만족하지 못한 경우에는 가능한 모든 조작을 수행하여 새로운 상태를 큐에 추가한다.
이 과정 중에서 이미 방문한 상태는 visited 로 파악하여 건너뛴다.
이번에는 change 함수인데,
1
2
3
4
5
6
7
8
9
10
public static boolean[] change(int idx, boolean[] cur, int n) {
boolean[] temp = Arrays.copyOf(cur, cur.length);
boolean flag = cur[idx];
for (int i = idx; i > 0; i--) {
temp[i] = temp[i - 1];
}
temp[0] = flag;
return temp;
}
이 함수는 카드 조작을 담당하는 메서드이다.
이 메서드는 주어진 카드 배열에서 특정 인덱스의 카드를 맨 앞으로 이동시키는 조작을 수행한다.
Arrays.copyOf 를 사용하여 현재 카드 배열의 복사본을 생성하고, 선택한 인덱스에서 카드를 뽑아 맨 앞으로 이동시키고, 나머지 카드들을 뒤로 밀어낸다.
즉, 시뮬레이션을 위한 함수이다.
마지막으로는 승리 조건을 확인하는 isWin 함수이다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static boolean isWin(boolean[] cur, int n) {
int[] score = new int[2];
for(int i = 0 ; i < n ; i += 2){
if(cur[i] == cur[i + 1]){
continue;
}
if(cur[i]){
score[0]++;
}else {
score[1]++;
}
}
return score[0] > score[1];
}
}
이 메서드는 주어진 카드 배열 상태에서 A가 승리하는지 여부를 확인한다.
짝수 인덱스마다 A와 B의 카드를 비교하여 점수를 계산하게 되고 A의 점수가 B보다 높으면 true, 반대인 경우 false를 리턴한다.
BFS를 활용해 모든 카드 배열을 탐색하고 A가 승리할 수 있는 최소 조작 횟수를 찾아낸다.
이때 입력의 크기가 작기 때문에, 이 알고리즘은 빠르게 답을 찾을 수 있다.
전체 소스코드는 다음과 같다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static void main(String[] args) throws java.io.IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int n = Integer.parseInt(br.readLine());
st = new StringTokenizer(br.readLine());
boolean[] isO = new boolean[2 * n];
for (int i = 0; i < 2 * n; i++) {
if (st.nextToken().charAt(0) == 'O') {
isO[i] = true;
}
}
int result = bfs(isO, 2 * n);
System.out.println(result);
}
public static int bfs(boolean[] isO, int n) {
int count = 0;
Queue<boolean[]> q = new LinkedList<>();
q.offer(isO);
Set<String> visited = new HashSet<>();
while (!q.isEmpty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
boolean[] cur = q.poll();
if (isWin(cur, n)) {
return count;
}
for (int j = 0; j < n; j++) {
boolean[] nxt = change(j, cur, n);
if (!visited.contains(Arrays.toString(nxt))) {
q.offer(nxt);
visited.add(Arrays.toString(nxt));
}
}
}
count++;
}
return -1;
}
public static boolean[] change(int idx, boolean[] cur, int n) {
boolean[] temp = Arrays.copyOf(cur, cur.length);
boolean flag = cur[idx];
for (int i = idx; i > 0; i--) {
temp[i] = temp[i - 1];
}
temp[0] = flag;
return temp;
}
public static boolean isWin(boolean[] cur, int n) {
int[] score = new int[2];
for(int i = 0 ; i < n ; i += 2){
if(cur[i] == cur[i + 1]){
continue;
}
if(cur[i]){
score[0]++;
}else {
score[1]++;
}
}
return score[0] > score[1];
}
}
이번 문제를 풀기 위해 참고할 블로그가 딱 하나 밖에 없었다.
해당 블로그에는 설명이 쓰여있지 않아 혼자 좀 앓았다.
여튼 혼자 이거저거 시도해보다가 안되가지고 헤맸는데, 간단한 설명의 문제일 수록 어려운거 같기도 하다.