-
[BOJ] 캐슬디펜스Algorithm/BOJ 2020. 2. 13. 15:06
[17135] 캐슬디펜스
https://www.acmicpc.net/problem/17135
- 게임이 진행되는 곳은 크기가 NXM인 격자판이다.
- 각 칸에 포함된 적의 수는 최대 하나이며, N+1행의 모든 칸에는 성이 있다.
- 성을 적에게서 지키기 위해 성이 있는 칸(N+1)에 궁수 3명을 배치하려고 한다.
- 궁수가 공격하는 적은 거리가 D이하인 적 중에서 가장 가까운 적이고 공격받은 적은 게임에서 제외된다.
- 궁수의 공격이 끝나면, 적은 아래로 한 칸 이동하며 성이 있는 칸으로 내려간 경우에는 게임에서 제외된다.
- 모든 적이 격자판에서 제외되면 게임이 끝난다.
- 입력 : N(행) M(열) D(거리 제한), NxM(격자판의 상태)
- 출력 : 궁수의 공격으로 제거할 수 있는 적의 최대 수
Solution
- permutation()으로 궁수의 자리를 바꿔가며 BFS로 궁수를 제거하였다.
- 문제의 조건은 최대한 많은 적을 죽이는 것이지만 가장 가까운 적을 우선으로 죽여야 하는 것이다.
- 세 명의 궁수가 동시에 죽일 수 있도록 구현하는 것이 중요하다.
소스코드
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.LinkedList;import java.util.Queue;import java.util.StringTokenizer;public class Main {static int n, m, d, answer;static int[][] map, copy, visited;static int[] a;static int[] dx = { 0, -1, 0 };static int[] dy = { -1, 0, 1 };static Queue<Node> q;static class Node {int x, y, step;public Node(int x, int y, int step) {this.x = x;this.y = y;this.step = step;}}public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));StringTokenizer st = new StringTokenizer(br.readLine());n = stoi(st.nextToken());m = stoi(st.nextToken());d = stoi(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] = stoi(st.nextToken());}}answer = Integer.MIN_VALUE;a = new int[3];permutation(0, 0);System.out.println(answer);}static void permutation(int depth, int start) {if (depth == 3) {simulation();return;}for (int i = start; i < m; i++) {a[depth] = i;permutation(depth + 1, i + 1);}}static void simulation() {copy();int count = 0;for (int j = 1; j <= n; j++) {for (int i = 0; i < a.length; i++) {count += bfs(new Node(n + 1, a[i], 0));}move();}answer = Math.max(answer, count);}static int bfs(Node node) {q = new LinkedList<>();q.offer(node);visited = new int[n + 2][m];visited[node.x][node.y] = 1;while (!q.isEmpty()) {Node cur = q.poll();for (int i = 0; i < 3; i++) {int nx = cur.x + dx[i];int ny = cur.y + dy[i];if (nx < 1 || ny < 0 || nx >= n + 1 || ny >= m)continue;if(visited[nx][ny] == 1)continue;if (copy[nx][ny] > 0 && cur.step < d) {if(copy[nx][ny] == 1) {copy[nx][ny] = 2;return 1;}else {return 0;}} else if (copy[nx][ny] == 0 && cur.step < d) {q.offer(new Node(nx, ny, cur.step + 1));visited[nx][ny] = 1;}}}return 0;}static void move() {for (int i = n; i > 0; i--) {copy[i] = copy[i - 1];for (int j = 0; j < m; j++) {if (copy[i][j] == 2)copy[i][j] = 0;}}}static void copy() {copy = new int[n + 2][m];for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {copy[i+1][j] = map[i][j];}}}static void print(int[][] a) {for (int i = 0; i < n + 2; i++) {for (int j = 0; j < m; j++) {System.out.print(a[i][j] + " ");}System.out.println();}System.out.println("------------");}static void print(int[] a) {for (int i = 0; i < a.length; i++) {System.out.print(a[i] + " ");}System.out.println();}static int stoi(String s) {return Integer.parseInt(s);}}cs 'Algorithm > BOJ' 카테고리의 다른 글
[BOJ] 패션왕 신해빈 (0) 2020.05.27 [BOJ] 연구소3 (0) 2020.04.28 [BOJ] 배열 돌리기 3 (0) 2020.02.11 [BOJ] 배열 돌리기 1 (0) 2020.02.10 [BOJ] 게리멘더링 (0) 2020.02.10