https://www.acmicpc.net/problem/17135
17135번: 캐슬 디펜스
첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다.
www.acmicpc.net
풀이
다음과 같은 흐름으로 문제를 풀었다.
1. 조합(mC3)을 사용하여 궁수 3명의 위치를 정한다.
2. 각 위치에 따라 처치하는 적의 수를 구한다.
2-1. 각 궁수마다 처치할 적을 선택한다.
2-2. 적을 처치한다.
2-3. 적을 한 칸 아래로 이동한다.
모든 적을 처치하거나, 적이 성으로 모두 이동할 때까지 2-1 ~ 2-3을 반복한다.
3. 모든 경우의 수에서 처치하는 적의 최대 수를 구한다.
main() 함수와 전역변수
main() 함수에서는 n, m, d, map을 입력받고 전체 적의 수(enemyCnt)를 구하고, locateDefense()를 호출한다.
static int n, m, d;
static int enemyCnt = 0, attackCnt = 0, maxCnt = 0; // 전체 적의 수, 현재 궁수들의 위치에서 처치하는 적의 수, 모든 경우의 수에서 처치하는 적의 최대 수
static int[][] map;
static boolean flag = false;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
d = Integer.parseInt(st.nextToken());
map = new int[n][m];
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < m; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
if (map[i][j] == 1) enemyCnt++;
}
}
int[] comb = new int[3];
locateDefense(0, 0, comb); // 조합을 사용하여 궁수의 위치를 정함
System.out.println(maxCnt);
}
void locateDefense(int idx, int start, int[] comb)
조합을 사용하여 궁수의 위치를 정한다.
궁수의 위치가 정해지면 map 배열을 복사한 copyMap을 생성하고 attack() 함수를 호출하여 처치한 적의 수(attackCnt)를 구한다.
모든 경우에서 처치한 적의 최대 수(maxCnt)와 attackCnt를 비교하여 최댓값을 업데이트한다.
maxCnt와 enemyCnt가 같다면 이미 구할 수 있는 최댓값이 나왔으므로 더 이상 다른 경우의 수를 계산할 필요가 없다.
public static void locateDefense(int idx, int start, int[] comb) {
// 최댓값이 나오면 더 이상 탐색 할 필요가 없다.
if (flag) return;
if (idx == 3) {
attackCnt = 0;
// map 배열을 복사
int[][] copyMap = new int[n][m];
for (int i = 0; i < n; i++)
copyMap[i] = Arrays.copyOfRange(map[i], 0, m);
// 공격
attack(comb, copyMap);
maxCnt = Math.max(maxCnt, attackCnt);
// 공격한 적의 수가 전체 적의 개수와 같다면, 더 이상 탐색을 할 필요가 없다.
if (maxCnt == enemyCnt) {
flag = true;
}
return;
}
// 중요: i < n이 아니라 i < m
for (int i = start; i < m; i++) {
comb[idx] = i;
locateDefense(idx+1, i+1, comb);
}
}
void attack(int[] pos, int[][] copyMap)
pos[]에는 궁수의 위치가 저장되어 있고, copyMap은 현재 게임이 진행되는 격자판이다. 이를 바탕으로 처치한 적의 수를 구하는 함수다.
각 궁수마다 처치할 적의 위치를 구하여 Set<Position>에 추가한다. 이 때 Set에 추가하는 이유는 여러 궁수가 같은 적을 공격할 수 있으므로 자동으로 중복을 처리하기 위해 Set을 사용하였다.
positions에 저장되어있는 적의 위치를 통해 적을 처치하고(copyMap[][] = 0), 적을 한 칸 아래로 이동시킨다.
attack() 함수를 재귀호출하여, 모든 적을 처치하거나 적이 성까지 모두 이동하기 전까지 위 과정을 반복한다.
public static void attack(int[] pos, int[][] copyMap) {
// 모든 적을 처치하거나 적이 성까지 모두 이동하면 종료
if (enemyCnt == attackCnt || isCompleted(copyMap)) return;
Set<Position> positions = new HashSet<>(); // 여러 궁수가 같은 적을 공격할 수 있으므로 set에 적의 위치 저장
// 각 궁수마다 처치할 적을 선택한다.
for (int idx = 0; idx < 3; idx++) {
int r = n, c = pos[idx];
int minD = Integer.MAX_VALUE, minR = n-1, minC = 0;
// 왼쪽부터 탐색
for (int j = 0; j < m; j++) {
for (int i = n-1; i >= 0; i--) {
if (copyMap[i][j] == 0) continue;
int distance = Math.abs(r - i) + Math.abs(c - j);
if (distance <= d && distance < minD) {
minD = distance;
minR = i; minC = j;
}
}
}
// 처치하는 적의 위치를 positions에 추가
if (minD != Integer.MAX_VALUE)
positions.add(new Position(minR, minC));
}
// 적 처치
attackCnt += positions.size();
for (Position p: positions) {
copyMap[p.x][p.y] = 0;
}
// 적을 아래 한 칸 내려오게 하기
for (int i = n-1; i >= 1; i--) {
copyMap[i] = Arrays.copyOfRange(copyMap[i-1], 0, m);
}
Arrays.fill(copyMap[0], 0);
attack(pos, copyMap);
}
public static boolean isCompleted(int[][] copyMap) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++)
if (copyMap[i][j] == 1) return false;
}
return true;
}
전체 코드
import java.util.*;
import java.io.*;
public class Main {
static int n, m, d;
static int enemyCnt = 0, attackCnt = 0, maxCnt = 0; // 전체 적의 수, 현재 궁수들의 위치에서 처치하는 적의 수, 모든 경우의 수에서 처치하는 적의 최대 수
static int[][] map;
static boolean flag = false;
static class Position {
int x;
int y;
public Position(int x, int y) {
this.x = x;
this.y = y;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
d = Integer.parseInt(st.nextToken());
map = new int[n][m];
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < m; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
if (map[i][j] == 1) enemyCnt++;
}
}
int[] comb = new int[3];
locateDefense(0, 0, comb); // 조합을 사용하여 궁수의 위치를 정함
System.out.println(maxCnt);
}
public static void locateDefense(int idx, int start, int[] comb) {
// 최댓값이 나오면 더 이상 탐색 할 필요가 없다.
if (flag) return;
if (idx == 3) {
attackCnt = 0;
// map 배열을 복사
int[][] copyMap = new int[n][m];
for (int i = 0; i < n; i++)
copyMap[i] = Arrays.copyOfRange(map[i], 0, m);
// 공격
attack(comb, copyMap);
maxCnt = Math.max(maxCnt, attackCnt);
// 공격한 적의 수가 전체 적의 개수와 같다면, 더 이상 탐색을 할 필요가 없다.
if (maxCnt == enemyCnt) {
flag = true;
}
return;
}
// 중요: i < n이 아니라 i < m
for (int i = start; i < m; i++) {
comb[idx] = i;
locateDefense(idx+1, i+1, comb);
}
}
public static void attack(int[] pos, int[][] copyMap) {
// 모든 적을 처치하거나 적이 성까지 모두 이동하면 종료
if (enemyCnt == attackCnt || isCompleted(copyMap)) return;
Set<Position> positions = new HashSet<>(); // 여러 궁수가 같은 적을 공격할 수 있으므로 set에 적의 위치 저장
// 각 궁수마다 처치할 적을 선택한다.
for (int idx = 0; idx < 3; idx++) {
int r = n, c = pos[idx];
int minD = Integer.MAX_VALUE, minR = n-1, minC = 0;
// 왼쪽부터 탐색
for (int j = 0; j < m; j++) {
for (int i = n-1; i >= 0; i--) {
if (copyMap[i][j] == 0) continue;
int distance = Math.abs(r - i) + Math.abs(c - j);
if (distance <= d && distance < minD) {
minD = distance;
minR = i; minC = j;
}
}
}
// 처치하는 적의 위치를 positions에 추가
if (minD != Integer.MAX_VALUE)
positions.add(new Position(minR, minC));
}
// 적 처치
attackCnt += positions.size();
for (Position p: positions) {
copyMap[p.x][p.y] = 0;
}
// 적을 아래 한 칸 내려오게 하기
for (int i = n-1; i >= 1; i--) {
copyMap[i] = Arrays.copyOfRange(copyMap[i-1], 0, m);
}
Arrays.fill(copyMap[0], 0);
attack(pos, copyMap);
}
public static boolean isCompleted(int[][] copyMap) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++)
if (copyMap[i][j] == 1) return false;
}
return true;
}
}
참고
728x90
'Algorithm 문제 풀이 > 백준' 카테고리의 다른 글
| [백준] 2579번 : 계단 오르기 - 자바[Java] (0) | 2023.08.03 |
|---|---|
| [백준] 2003번 : 수들의 합 - 자바[Java] (0) | 2023.07.25 |
| [백준] 16637번 : 괄호 추가하기 - 자바[Java] (0) | 2023.06.27 |
| [백준] 17070번 : 파이프 옮기기 1 - 자바[Java] (0) | 2023.06.27 |
| [백준] 2636번 : 치즈 - 자바[Java] (0) | 2023.06.24 |
