17135번: 캐슬 디펜스
첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다.
www.acmicpc.net
알고리즘 분류는 bfs지만 조합 + 정렬 + 시뮬레이션 + 구현 등 사용해야할 기법이 많았습니다.
제가 처음 접근한 방법은
우선 조합으로 궁수가 있을 자리를 모두 구해준 다음
bfs로 4방향 탐색하여 공격가능한 적을 모두 담아놓고 정렬하여 맨 첫번째에 있는 적만 제거하였고
그 다음 적들을 모두 아래로 내려 다음 bfs탐색을 하는 방식이었습니다.
위의 방법으로 AC를 받았지만 시간적인 손해가 많다는 생각이 들었고, 시간을 줄이기위해 다른 방법을 생각하였습니다.
궁수는 항상 N + 1번째 행에 있기때문에 밑을 볼 필요가 없습니다. 그래서 왼쪽, 위, 오른쪽만 탐색하면 됩니다.
여기서 문제 조건을 보시면 가장 가까운 적이 여러명이면 가장 왼쪽에 있는 적을 공격한다고 나와있습니다.
위의 조건에서 왼쪽 -> 위 -> 오른쪽 방향 순서로 탐색하면 무조건 공격해야할 대상을 먼저 찾는다는 결론이 나왔습니다. 이제 정렬은 사용하지 않아도됩니다.
그 다음 여러명의 궁수가 한명의 적을 공격할 수 있기때문에 궁수가 공격할 대상을 찾으면
boolean배열을 사용하여 true로 바꿔주었고, 이중 for문으로 true인 좌표의 list를 0으로 바꿔주었지만
int배열을 사용하여 모든 좌표를 다 넣어주었고, 하나의 for문으로 해결할 수 있었습니다.
마지막으로 적을 제거하고 난 후에 이중 for문을 돌려서 적이 모두 제거되었는지 확인하였습니다.
제거되었으면 break를 해주고, 아니면 적들을 아래로 내려야합니다.
하지만 저는 적들을 아래로 내리는것보다 궁수를 위로 올리는 것이 시간상 효율적이라는 것을 깨닫고 궁수를 위로 올리기 위해 n--를 하였습니다.
최종적으로 저의 로직은 이렇습니다.
1. 조합으로 궁수를 배치
2. bfs로 3방향 탐색하여 공격할 수 있는 적을 탐색 (적을 찾거나 D보다 거리가 커지면 break)
3. 2번에서 찾은 적 제거
4. 적이 모두 제거되었는지 확인
5. 적이 모두 제거되었으면 break, 아니면 궁수 한 칸 위로 이동(n--)
자바에서 Collection사용이 많아지면 시간적으로 비효율적이라고 생각해서 배열을 최대한 사용하였습니다.
|
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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static boolean visit[][];
static int direct[][] = { { 0, -1 }, { -1, 0 }, { 0, 1 } };
static int list[][], copylist[][], attacker[], rkill[][];
static int N, M, D, ans, kidx;
static void bfs() {
int n = N;
int sum = 0;
Deque<int[]> dq = new ArrayDeque<int[]>();
ArrayList<int[]> kill = new ArrayList<>();
while (true) {
for (int k = 0; k < 3; k++) {
dq.addLast(new int[] { n, attacker[k], 0 });
for (int i = 0; i < n; i++)
Arrays.fill(visit[i], false);
while (!dq.isEmpty()) {
int x = dq.peekFirst()[0];
int y = dq.peekFirst()[1];
int cnt = dq.pollFirst()[2];
if (cnt == D) {
dq.clear();
break;
}
boolean chk = false;
for (int i = 0; i < 3; i++) {
int nx = x + direct[i][0];
int ny = y + direct[i][1];
if (nx < 0 || ny < 0 || nx >= n || ny >= M)
continue;
if (visit[nx][ny])
continue;
if (copylist[nx][ny] == 1) {
chk = true;
kill.add(new int[] { nx, ny, cnt + 1 });
break;
} else {
dq.addLast(new int[] { nx, ny, cnt + 1 });
visit[nx][ny] = true;
}
}
if (chk)
break;
}
dq.clear();
if (kill.isEmpty())
continue;
rkill[kidx][0] = kill.get(0)[0];
rkill[kidx++][1] = kill.get(0)[1];
kill.clear();
}
for (int i = 0; i < kidx; i++) {
if (copylist[rkill[i][0]][rkill[i][1]] == 1) {
copylist[rkill[i][0]][rkill[i][1]] = 0;
sum++;
}
}
kidx = 0;
boolean allkill = false;
for (int i = 0; i < n; i++) {
for (int j = 0; j < M; j++) {
if (copylist[i][j] == 1) {
allkill = true;
break;
}
}
if (allkill)
break;
}
if (!allkill)
break;
n--;
}
ans = Math.max(ans, sum);
}
static void func(int idx, int cnt) {
if (cnt == 3) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++)
copylist[i][j] = list[i][j];
}
bfs();
return;
}
for (int i = idx; i < M; i++) {
attacker[cnt] = i;
func(i + 1, cnt + 1);
}
}
static void input() throws Exception {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
D = Integer.parseInt(st.nextToken());
list = new int[N][M];
copylist = new int[N][M];
attacker = new int[3];
visit = new boolean[N][M];
rkill = new int[226][2];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < M; j++) {
list[i][j] = Integer.parseInt(st.nextToken());
}
}
}
public static void main(String[] args) throws Exception {
input();
func(0, 0);
System.out.println(ans);
}
}
|
cs |
'algorithm > bfs' 카테고리의 다른 글
| boj 1525 퍼즐 (0) | 2021.02.19 |
|---|---|
| boj 7576 토마토 (0) | 2021.02.19 |
| boj 16236 아기 상어 (0) | 2021.02.14 |
| boj 10026 적록색약 (0) | 2021.02.13 |
| boj 2206 벽 부수고 이동하기 (0) | 2021.02.13 |