https://www.acmicpc.net/problem/17135
17135번: 캐슬 디펜스
첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다.
www.acmicpc.net
#
문제
캐슬 디펜스는 성을 향해 몰려오는 적을 잡는 턴 방식의 게임이다. 게임이 진행되는 곳은 크기가 N×M인 격자판으로 나타낼 수 있다. 격자판은 1×1 크기의 칸으로 나누어져 있고, 각 칸에 포함된 적의 수는 최대 하나이다. 격자판의 N번행의 바로 아래(N+1번 행)의 모든 칸에는 성이 있다.
성을 적에게서 지키기 위해 궁수 3명을 배치하려고 한다. 궁수는 성이 있는 칸에 배치할 수 있고, 하나의 칸에는 최대 1명의 궁수만 있을 수 있다. 각각의 턴마다 궁수는 적 하나를 공격할 수 있고, 모든 궁수는 동시에 공격한다. 궁수가 공격하는 적은 거리가 D이하인 적 중에서 가장 가까운 적이고, 그러한 적이 여럿일 경우에는 가장 왼쪽에 있는 적을 공격한다. 같은 적이 여러 궁수에게 공격당할 수 있다. 공격받은 적은 게임에서 제외된다. 궁수의 공격이 끝나면, 적이 이동한다. 적은 아래로 한 칸 이동하며, 성이 있는 칸으로 이동한 경우에는 게임에서 제외된다. 모든 적이 격자판에서 제외되면 게임이 끝난다.
게임 설명에서 보다시피 궁수를 배치한 이후의 게임 진행은 정해져있다. 따라서, 이 게임은 궁수의 위치가 중요하다. 격자판의 상태가 주어졌을 때, 궁수의 공격으로 제거할 수 있는 적의 최대 수를 계산해보자.
격자판의 두 위치 (r1, c1), (r2, c2)의 거리는 |r1-r2| + |c1-c2|이다.
#난이도
Gold 4
#알고리즘
구현, 그래프이론 , 부루트포스 알고리즘, 시뮬레이션
#나의 풀이 방법
나는 빡구현 문제를 제일 싫어한다.. 왜냐하면 코드의 양이 다른 유형의 코테보다 많고 상당히 귀찮기 때문이다...
하지만 코테 유형중에 빡구현 문제가 상당히 많이 출제되므로 연습해보고자 한다...
일단 문제 이해 자체는 어렵지 않으나 구현하는데 꽤 많은 부분이 고려해야 될 것이 많다.
구현해야 할 것들을 나열한다면
1. 궁수들의 위치
2. 궁수들이 누구를 공격하는가
2-1. 가까운 적부터
2-2. 거리가 가깝다면 왼쪽부터..
3. 다음 턴
4. 적들이 모두 소멸됐는가?
궁수들의 위치는 순열을 사용한 백트래킹으로 구현 하였다.
주어진 배열에 한줄을 더 만들어 궁수들의 위치를 순열로 나두고 궁수가 3명(고정)이 될 경우,
시뮬레이션을 가동한다.
public static void back_track(int[][] castle,int hawk) {
if(hawk == 3) {
for(int i=0; i<enemy_position.size(); i++) {
castle[enemy_position.get(i).i][enemy_position.get(i).j] = 1;
}
simulation(castle);//시뮬레이션 시작
return;
}//궁수 배치가 완료될 경우,
for(int j=0; j<castle[0].length; j++) {
if(castle[castle.length-1][j] == 0) {
castle[castle.length-1][j] = 2;//궁수의 위치에 2를 대입한다.
back_track(castle,hawk+1);
castle[castle.length-1][j] = 0;//끝나면 다시 원위치
}
}//궁수들 순열대로 배치
}
적이 소멸될때까지, 죽이기 -> 다음턴에 과정을 반복한 후, 죽인 적들에 대한 max를 업데이트 해준다.
public static void simulation(int[][] castle) {
hawk_eye = new ArrayList<>();//궁수들 위치를 담을 arraylist
enemy_kill = 0;//죽인 횟수,초기화
for(int i=0; i<castle[0].length; i++) {
if(castle[castle.length-1][i] == 2) {
hawk_eye.add(new Node(castle.length-1,i));
}
}//궁수들의 위치를 hawk_eye에 삽입
while(!check(castle)){
kill_position = new ArrayList<>();//죽일 적들에 좌표를 담는 arraylist
castle = kill(castle);//적 죽이기
castle = next_turn(castle);//다음턴
}//적이 처치될때까지 시뮬레이션
if(enemy_kill > max)
max = enemy_kill;
//매판 마다 죽인 적이 제일 많을 경우를 기록하기 위하여 매판마다 비교후 대입
}
일단 kill 메소드를 보자면,
public static int[][] kill(int[][] castle){
for(int i=0; i<hawk_eye.size(); i++) {
bfs(hawk_eye.get(i).i,hawk_eye.get(i).j,castle);
}//궁수의 위치에 가장 가까운 적 위치 탐색
boolean[][] overlap = new boolean[castle.length][castle[0].length];
for(int i=0; i<kill_position.size(); i++) {
if(!overlap[kill_position.get(i).i][kill_position.get(i).j]) {
overlap[kill_position.get(i).i][kill_position.get(i).j] = true;
castle[kill_position.get(i).i][kill_position.get(i).j] = 0;//적 처치 ,0으로 초기화
enemy_kill++;//죽인적 +1
}//타켓이 겹칠경우, 죽인 횟수를 중복되지 않기 위해 boolean형 2차원 배열 선언
}
return castle;
}
public static void bfs(int i,int j,int[][] castle) {
Queue<Node> queue = new LinkedList<>();
queue.add(new Node(i,j));
boolean[][] visited = new boolean[castle.length][castle[0].length];
visited[i][j] = true;
while(!queue.isEmpty()) {
Node n = queue.poll();
if(castle[n.i][n.j] == 1) {
kill_position.add(new Node(n.i,n.j));
return;
}//적을 발견했을 경우,적 위치 arraylist 대입 후 종료
if(range_in(castle,n.i,n.j-1) && D >= distance(n.i,n.j-1,i,j) && !visited[n.i][n.j-1]){
visited[n.i][n.j-1] = true;
queue.add(new Node(n.i,n.j-1));
}//왼쪽
if(range_in(castle,n.i-1,n.j) && D >= distance(n.i-1,n.j,i,j) && !visited[n.i-1][n.j]){
visited[n.i-1][n.j] = true;
queue.add(new Node(n.i-1,n.j));
}//위쪽
if(range_in(castle,n.i,n.j+1) && D >= distance(n.i,n.j+1,i,j) && !visited[n.i][n.j+1]){
visited[n.i][n.j+1] = true;
queue.add(new Node(n.i,n.j+1));
}//오른쪽
}
}
궁수들의 위치를 담은 정보를 차례대로 bfs로 적 위치를 탐색한다.
bfs로 탐색하는 이유는
1. 가장 가까운
2. 거리가 같다면 왼쪽부터이기 때문이다
따라서 bfs로 왼쪽 위 오른쪽 순으로 탐색한다면 위 조건들을 다 충족할 수 있기 때문에 bfs로 구현하였고,
kill_enemy 리스트에 적위치가 담겨져 있다면 적을 죽이는 과정을 진행한다. 이 과정에서 궁수의 서로 죽이는 적이 같다면 boolean형 2차원 배열을 사용하여 죽인적이 중복되지 않도록 한다.
public static int[][] next_turn(int[][] castle) {
for(int i=0; i<castle[0].length; i++) {
castle[castle.length-2][i] = 0;
}//마지막 열
for(int i=castle.length-2; i>0; i--) {
for(int j=0; j<castle[0].length;j++) {
if(castle[i-1][j] == 1) {
castle[i][j] = 1;
castle[i-1][j] = 0;
}
}
}
return castle;
}//다음차례가 되면 적들이 한칸씩 내려가는 메소드남아 있는 적이 있다면 한칸씩 밑으로 내려오기 때문에 아래에서 부터 탐색하여 적 위치를 초기화 한다.
적이 있을 수 있는 위치 마지막 행에 있는 적은 사라지므로 만약 적이 있다면 0으로 초기화 하고
나머지 행들은 위에 적 즉 1있다면 밑으로 1을 초기화 시킨 후 , 원래 있는 위치를 0으로 초기화 시켜주는 작업으로
다음 차례를 구현한다.
#전체 코드
import java.util.*;
//2t
public class Main {
static int D;
static int max = 0;//물리칠수 있는 적의 최대 갯수
static int enemy_kill = 0;
static ArrayList<Node> enemy_position = new ArrayList<>();
static ArrayList<Node> hawk_eye = new ArrayList<>();
static ArrayList<Node> kill_position = new ArrayList<>();
public static int distance(int x1,int y1,int x2,int y2) {
return Math.abs(x2-x1) + Math.abs(y2-y1);
}//거리계산
public static int[][] next_turn(int[][] castle) {
for(int i=0; i<castle[0].length; i++) {
castle[castle.length-2][i] = 0;
}//마지막 열
for(int i=castle.length-2; i>0; i--) {
for(int j=0; j<castle[0].length;j++) {
if(castle[i-1][j] == 1) {
castle[i][j] = 1;
castle[i-1][j] = 0;
}
}
}
return castle;
}//다음차례가 되면 적들이 한칸씩 내려가는 메소드
public static int[][] kill(int[][] castle){
for(int i=0; i<hawk_eye.size(); i++) {
bfs(hawk_eye.get(i).i,hawk_eye.get(i).j,castle);
}//궁수의 위치에 가장 가까운 적 위치 탐색
boolean[][] overlap = new boolean[castle.length][castle[0].length];
for(int i=0; i<kill_position.size(); i++) {
if(!overlap[kill_position.get(i).i][kill_position.get(i).j]) {
overlap[kill_position.get(i).i][kill_position.get(i).j] = true;
castle[kill_position.get(i).i][kill_position.get(i).j] = 0;//적 처치 ,0으로 초기화
enemy_kill++;//죽인적 +1
}//타켓이 겹칠경우, 죽인 횟수를 중복되지 않기 위해 boolean형 2차원 배열 선언
}
return castle;
}
public static void bfs(int i,int j,int[][] castle) {
Queue<Node> queue = new LinkedList<>();
queue.add(new Node(i,j));
boolean[][] visited = new boolean[castle.length][castle[0].length];
visited[i][j] = true;
while(!queue.isEmpty()) {
Node n = queue.poll();
if(castle[n.i][n.j] == 1) {
kill_position.add(new Node(n.i,n.j));
return;
}//적을 발견했을 경우,적 위치 arraylist 대입 후 종료
if(range_in(castle,n.i,n.j-1) && D >= distance(n.i,n.j-1,i,j) && !visited[n.i][n.j-1]){
visited[n.i][n.j-1] = true;
queue.add(new Node(n.i,n.j-1));
}//왼쪽
if(range_in(castle,n.i-1,n.j) && D >= distance(n.i-1,n.j,i,j) && !visited[n.i-1][n.j]){
visited[n.i-1][n.j] = true;
queue.add(new Node(n.i-1,n.j));
}//위쪽
if(range_in(castle,n.i,n.j+1) && D >= distance(n.i,n.j+1,i,j) && !visited[n.i][n.j+1]){
visited[n.i][n.j+1] = true;
queue.add(new Node(n.i,n.j+1));
}//오른쪽
}
}
public static boolean range_in(int[][] castle,int i,int j) {
if((-1 < i && i < castle.length) &&(-1 < j && j < castle[0].length))
return true;
else
return false;
}
public static void simulation(int[][] castle) {
hawk_eye = new ArrayList<>();//궁수들 위치를 담을 arraylist
enemy_kill = 0;//죽인 횟수,초기화
for(int i=0; i<castle[0].length; i++) {
if(castle[castle.length-1][i] == 2) {
hawk_eye.add(new Node(castle.length-1,i));
}
}//궁수들의 위치를 hawk_eye에 삽입
while(!check(castle)){
kill_position = new ArrayList<>();//죽일 적들에 좌표를 담는 arraylist
castle = kill(castle);//적 죽이기
castle = next_turn(castle);//다음턴
}//적이 처치될때까지 시뮬레이션
if(enemy_kill > max)
max = enemy_kill;
//매판 마다 죽인 적이 제일 많을 경우를 기록하기 위하여 매판마다 비교후 대입
}
public static boolean check(int[][] castle) {
for(int i=0; i<castle.length-1; i++) {
for(int j=0; j<castle[0].length; j++) {
if(castle[i][j] == 1) {
return false;
}
}
}
return true;
}//적이 다 제거됐는지 확인하는 메소드
public static void back_track(int[][] castle,int hawk) {
if(hawk == 3) {
for(int i=0; i<enemy_position.size(); i++) {
castle[enemy_position.get(i).i][enemy_position.get(i).j] = 1;
}
simulation(castle);//시뮬레이션 시작
return;
}//궁수 배치가 완료될 경우,
for(int j=0; j<castle[0].length; j++) {
if(castle[castle.length-1][j] == 0) {
castle[castle.length-1][j] = 2;//궁수의 위치에 2를 대입한다.
back_track(castle,hawk+1);
castle[castle.length-1][j] = 0;//끝나면 다시 원위치
}
}//궁수들 순열대로 배치
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int M = sc.nextInt();
D = sc.nextInt();//궁수의 거리 제한
int[][] castle = new int[N+1][M];
for(int i=0; i<N; i++) {
for(int j=0; j<M; j++) {
castle[i][j] = sc.nextInt();
if(castle[i][j] == 1) {
enemy_position.add(new Node(i,j));
}//궁수와 적 간의 거리 계산을 위해 enemy_position이라는 arraylist를 만듬
}
}
back_track(castle,0);
System.out.println(max);
}
}
class Node{
int i;
int j;
Node(int i,int j){
this.i = i;
this.j = j;
}
}
사실 구현 하는데에 있어서 제일 힘든점은 다른 알고리즘 유형처럼 유형이 일정하지 않고, (물론 풀다보면 익숙해지겠지만..) 구현해야 하는 부분들을 일일이 손으로 직접 코딩하여 만들어야 한다는 것이다. (따라서 시간도 꽤 많이 걸림..)
하지만 연습만 계속 한다면 시간을 줄일 수 있으므로 많이 풀어보자... 화이팅....
'알고리즘 문제' 카테고리의 다른 글
| 백준 1499번) 수리공 항승 JAVA (0) | 2022.03.17 |
|---|---|
| 백준 14891번) 톱니바퀴1 JAVA (0) | 2022.02.21 |
| 백준 1455번) 뒤집기2 JAVA (0) | 2022.02.20 |
| (백준 12904번) A와 B (0) | 2022.02.07 |
| (JAVA) 백준 1911번, 흙길 보수하기 (0) | 2022.02.04 |