백준 12869번 : 뮤탈리스크
이번 문제는 스타크래프트 게임과 연관 지어 작성된 문제이다.
뮤탈리스크가 scv를 공격할 수 있으며, 뮤탈리스크는 한 번에 세 개의 개체를 공격한다.
뮤탈리스크의 공격은 다음과 같다.
- 첫 번째로 공격받는 SCV는 체력 9를 잃는다.
- 두 번째로 공격받는 SCV는 체력 3을 잃는다.
- 세 번째로 공격받는 SCV는 체력 1을 잃는다.
이러한 공격이 진행되었을 경우, n개의 scv를 전부 처치하는데에 몇 회 공격이 필요한지 리턴하는 문제이다.
입력은 첫 째줄에 scv의 수가 입력되고, 둘 째줄에 n개의 scv의 체력이 주어지며 scv의 체력은 60보다 같거나 작은 자연수이다.
가장 먼저 문제를 풀기 위해 멤버 변수를 선언했다.
각 멤버 변수는 다음과 같다.
1
2
3
4
5
6
7
8
9
public class Main {
static int[][] damage = new int[][]{
{9, 3, 1}, {9, 1, 3},
{3, 9, 1}, {3, 1, 9},
{1, 3, 9}, {1, 9, 3}
};
static boolean[][][] visited;
static int[] scv;
static int n;
damage 배열은 뮤탈리스크 공격의 모든 경우의 수를 작성한 것이다.
3번 공격, 3개의 데미지를 하드코딩으로 표현한 것이다.
그 다음 visited 배열은 특정 scv의 체력 조합을 방문했는지 여부를 추적하기 위한 배열이다.
scv 배열은 각 scv의 체력을 저장하고 n은 scv의 수를 의미한다.
그 다음으로는 main 함수이다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static void main(String[] args) throws java.io.IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
scv = new int[3];
visited = new boolean[61][61][61];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
scv[i] = Integer.parseInt(st.nextToken());
}
System.out.println(bfs());
}
메인 함수에서는 BufferedReader로 각 입력 값을 받아온다.
scv 배열의 크기 같은 경우는 문제에서 최대 3개의 scv가 입력될 수 있다고 명시되어 있기 때문에 3이라고 크기를 지정했으며, 모든 경우를 다루기 위해 배열의 크기를 3으로 고정한다.
만약 n으로 크기를 유동적으로 만든다면 배열 인덱스 범위를 벗어나게 될 수 있다.
그 다음으로는 scv 배열에 입력 받은 각 scv의 체력을 삽입하고 bfs를 진행한다.
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() {
Queue<int[]> q = new LinkedList<>();
q.offer(new int[]{scv[0], scv[1], scv[2], 0}); // scv 체력 + 공격 횟수
visited[scv[0]][scv[1]][scv[2]] = true;
while (!q.isEmpty()) {
int[] cur = q.poll();
if (cur[0] == 0 && cur[1] == 0 && cur[2] == 0) {
return cur[3]; // 모든 scv가 파괴되었다면 현재 공격 횟수 반환
}
// 가능한 모든 공격 조합
for (int[] attack : damage) {
int a = Math.max(0, cur[0] - attack[0]);
int b = Math.max(0, cur[1] - attack[1]);
int c = Math.max(0, cur[2] - attack[2]);
if (!visited[a][b][c]) {
visited[a][b][c] = true;
q.offer(new int[]{a, b, c, cur[3] + 1});
}
}
}
// 더미
return -1;
}
bfs 탐색을 시작하면서 큐에는 각 scv의 체력 상태와 현재까지의 공격횟수를 저장한다.
그 다음으로는 visited 배열을 활용하여 각 체력 상태가 이미 큐에 추가가 되었었는지 추적한다.
이를 통해 각 체력 상태에 대한 중복 여부 체크를 할 수 있다.
본격적으로 큐가 빌 때까지 탐색을 진행한다.
큐에서 현재 체력들과 공격 횟수 배열을 cur 배열에 담는다.
만약 큐에서 추출한 이 cur 배열에서 모든 scv의 체력이 0이라면 공격이 끝난 것이기 때문에 현재까지의 공격 횟수를 리턴면 종료한다.
강화 for문에서는 모든 가능한 공격 조합에 대해 탐색한다.
9, 3, 1 의 데메지를 주는 과정을 반복하는 것인데, 여기서 Math 클래스의 max 함수로 0과 비교하는 이유는 scv의 체력이 음수로 전환되어 예상치 못한 예외를 방지하기 위함이다.
각 공격에 대한 연산이 끝났다면, 해당 체력에 대해 방문했는지 여부를 체크하고 방문하지 않았다면 방문 여부를 true로 변경하고 현재 체력 상태를 큐에 삽입하고 공격 횟수를 1회 늘린다.
이로써 bfs 탐색은 완료되었다.
마지막의 -1은 int 타입 반환으로 컴파일 에러를 피하고, scv 체력을 모두 소진할 수 없는 경우 -1을 리턴하게 한다.
다만 일반적으로 -1을 리턴될 일이 없다.
전체 소스코드는 다음과 같다.
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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int[][] damage = new int[][]{
{9, 3, 1}, {9, 1, 3},
{3, 9, 1}, {3, 1, 9},
{1, 3, 9}, {1, 9, 3}
};
static boolean[][][] visited;
static int[] scv;
static int n;
public static void main(String[] args) throws java.io.IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
scv = new int[3];
visited = new boolean[61][61][61];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
scv[i] = Integer.parseInt(st.nextToken());
}
System.out.println(bfs());
}
public static int bfs() {
Queue<int[]> q = new LinkedList<>();
q.offer(new int[]{scv[0], scv[1], scv[2], 0}); // scv 체력 + 공격 횟수
visited[scv[0]][scv[1]][scv[2]] = true;
while (!q.isEmpty()) {
int[] cur = q.poll();
if (cur[0] == 0 && cur[1] == 0 && cur[2] == 0) {
return cur[3]; // 모든 scv가 파괴되었다면 현재 공격 횟수 반환
}
// 가능한 모든 공격 조합
for (int[] attack : damage) {
int a = Math.max(0, cur[0] - attack[0]);
int b = Math.max(0, cur[1] - attack[1]);
int c = Math.max(0, cur[2] - attack[2]);
if (!visited[a][b][c]) {
visited[a][b][c] = true;
q.offer(new int[]{a, b, c, cur[3] + 1});
}
}
}
// 더미
return -1;
}
}
이번 문제는 가능한 모든 공격 조합 부분 때문에 헷갈렸다.
결국 공격 경우의 수를 직접 만들어내긴했는데 더 스마트한 방법이 있을 것이다.