[백준] G4 17135 캐슬 디펜스 (java)

https://www.acmicpc.net/problem/17135

17135번: 캐슬 디펜스

 

풀이

 

0) 준비물

• 적들을 담을 클래스 Enemy <- (d의 오름차순>c의 오름차순)
• 궁수를 담을 리스트 archers
• 적들을 담을 리스트 enemies
• 최대 kill수를 저장할 maxKill
• 궁수를 배치할 조합 함수 allocateArcher()

1) 조합을 돌려 나올수 있는 모든 궁수의 배치를 뽑는다.

2) 1에서 나온 모든 케이스를 계산한다.

 

주의사항

 

1) 같은 적을 여러명의 궁수가 쏠 수 있다. 따라서 가장 가까운 적을 바로 죽이지 모든 궁수가 표식을 마친후 죽여야한다.

2) List를 복사할때 뭔짓을 해도 얕은 복사가 된다. (add(), addAll(), ArrayList(enemies), 등등) 따라서 일일이 하나씩 new를 통해 넣어줬다. <- 공부를 해야할 것 같다.

 

package com.baekJoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.StringTokenizer;

public class BJ_G4_17135_캐슬디펜스2 {
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tokens;
	static int N,M,D, maxKill, totalEnemy;
	static List<Integer> archers = new LinkedList<>();
	static List<Enemy> enemies = new ArrayList<>();
	public static void main(String[] args) throws NumberFormatException, IOException {
		input = new BufferedReader(new StringReader(src));
		tokens = new StringTokenizer(input.readLine());
		N = Integer.parseInt(tokens.nextToken());
		M = Integer.parseInt(tokens.nextToken());
		D = Integer.parseInt(tokens.nextToken());
		for(int r=0; r<N; r++) {
			tokens = new StringTokenizer(input.readLine());
			for(int c=0; c<M; c++) {
				if(Integer.parseInt(tokens.nextToken()) == 1) {
					enemies.add(new Enemy(r, c, 0,false));
					totalEnemy++;
				}
			}	
		}
		allocateArcher(0,0);
		System.out.println(maxKill);
	}
	
	private static void allocateArcher(int start, int cnt) { // 궁수 배치
		if(cnt == 3) {
			defence(enemies);
			return;
		}
		for(int i=start; i<M; i++) {
			archers.add(i);
			allocateArcher(i+1, cnt+1);
			archers.remove(archers.size()-1);
		}
	}
	
	private static void defence(List<Enemy> enemies) {
		// 0. kill = 0
		// 1. 모든 궁수가 죽일 적을 찾는다.
		// 2. 적을 죽인다. // kill++ 최대값이 곧 정답이다.
		// 3. 적들이 1칸 전진한다. // 범위를 넘은 적은 놓친 적이다. 
		// 4. 1~3을 반복, 적들이 존재하지 않으면 탈출. 
		List<Enemy> tempList = new ArrayList<>();
		for(int i=0; i<enemies.size(); i++) {
			tempList.add(new Enemy(enemies.get(i).r, enemies.get(i).c, 0, false));
		}
		int miss = 0, kill = 0;
		while(true) {
			if(kill > maxKill) {
				maxKill = kill;
			}
			if(tempList.isEmpty()) {
				break;
			}
			for(int i=0; i<archers.size(); i++) { // 조준
				for(int j=0; j<tempList.size(); j++) {
					Enemy front = tempList.get(j);
					tempList.get(j).d = Math.abs(front.r-N) + Math.abs(front.c - archers.get(i));
				}
				Collections.sort(tempList);
				if(tempList.get(0).d <= D) {
					tempList.get(0).isAimed = true;
				}
			}
			
			for(int i=0; i<tempList.size(); i++) {
				if(tempList.get(i).isAimed) {
					tempList.remove(i--);
					kill++;
				}
			}
			for(int i=0; i<tempList.size(); i++) {
				int nr = tempList.get(i).r+1;
				int nc = tempList.get(i).c;
				if(isIn(nr, nc)) {
					tempList.get(i).r++;
				}else {
					tempList.remove(i--);
				}
			}
		}
	}
	
	static class Enemy implements Comparable<Enemy>{
		int r;
		int c;
		int d;
		boolean isAimed;
		
		public Enemy(int r, int c, int d, boolean isAimed) {
			super();
			this.r = r;
			this.c = c;
			this.d = d;
			this.isAimed = isAimed;
		}

		@Override
		public String toString() {
			return "Enemy [r=" + r + ", c=" + c + ", d=" + d + ", isAimed=" + isAimed + "]";
		}

		@Override
		public int compareTo(Enemy o) {
			if(this.d == o.d) {
				return Integer.compare(this.c, o.c);
			}
			return Integer.compare(this.d, o.d);
		}
	}
	
	static boolean isIn(int r, int c) {
		return (r>=0 && c>=0 && r<N && c<M);
	}

	static String src =
			"5 5 5\r\n"
			+ "1 1 1 1 1\r\n"
			+ "1 1 1 1 1\r\n"
			+ "1 1 1 1 1\r\n"
			+ "1 1 1 1 1\r\n"
			+ "1 1 1 1 1";
}

 

후기

 

 나태함 때문에 풀다말다를 반복하다 결국 각잡고 풀었다.

처음 시도는

1. 조합을 통해 궁수를 배치한다.
2. 이차원 배열을 통해 모든 궁수가 죽일 적을 찾는다. <- 이 때, BFS를 통해 찾는다. (최대 거리 D 만큼.) 만약 0이 아닌 숫자가 나오면 3으로 바꾼다.
3. 이차원 배열을 탐색해 3이 나오면 kill수를 1 추가하고 0으로 바꾼다.
4. 적들이 한칸씩 전진한다.
   1. 이차원 배열을 탐색해(아래서부터) 1이면 0으로 바꾸고 아래칸을 1로 바꾼다.
   2. 만약 맨 밑칸일 경우 0으로 바꾸기만 한다.
5. 2~3을 N 번 반복한다.
6. 최대 kill수를 출력한다.

하지만 이차원 배열을 계속 탐색하는것, BFS를 탐색하는것이 조금 오래걸리지 않을까.. 고민하고 결국 이차원 배열말고 List를 쓰기로 했다.

list를 복사하여 모든 케이스를 적용하는 도중 문제가 발생했다.

분명히 복사한 list를 조작했는데 원본 list가 같이 변경된것이다. 이것이 객체의 깊은복사와 얕은복사의 차이였는데 이는 다음 글에서 조금더 자세히 정리해봐야겠다.

여튼 list를 이용해서 정답을 도출해 내는것에 성공했고 깊은 복사와 얕은 복사에 대하여 공부한 뒤에 이차원 배열과 BFS로도 풀어봐야할 것 같다.

시간은 아쉽게도 이차원 배열로 푼 사람들이 더 빨랐다ㅜㅜ

 

추가 (08.05)

혹시 몰라서 처음 아이디어로 다시 풀어봤다.

package com.baekJoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BJ_G4_17135_캐슬디펜스3 {
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tokens;
	static int N,M,D,map[][],temp[][], maxKill;
	static boolean isVisited[][];
	public static void main(String[] args) throws NumberFormatException, IOException {
		input = new BufferedReader(new StringReader(src));
		tokens = new StringTokenizer(input.readLine());
		N = Integer.parseInt(tokens.nextToken());
		M = Integer.parseInt(tokens.nextToken());
		D = Integer.parseInt(tokens.nextToken());
		map = new int[N][M];
		temp = new int[N][M];
		for(int r=0; r<N; r++) {
			tokens = new StringTokenizer(input.readLine());
			for(int c=0; c<M; c++) {
				map[r][c] = Integer.parseInt(tokens.nextToken());
			}	
		}
		for(int i=0; i<M-2; i++) {
			for(int j=i+1; j<M-1; j++) {
				for(int k=j+1; k<M; k++) {
					defence(i, j, k);
				}	
			}	
		}
		System.out.println(maxKill);
	}
	
	private static void defence(int i, int j, int k) {
		int kill = 0;
		for(int r=0; r<N; r++) {
			for(int c=0; c<M; c++) {
				temp[r][c] = map[r][c];
			}	
		}
		for(int t = 0; t<N; t++) {
			bfs(i);
			bfs(j);
			bfs(k);
			kill = killAndMove(kill);
		}
		if(maxKill < kill) {
			maxKill = kill;
		}
	}

	private static int killAndMove(int kill) {
		for(int r=N-1; r>=0; r--) { // 앞으로 한칸씩 전진하므로 뒤에서부터 해야함
			for(int c=0; c<M; c++) {
				if(temp[r][c] == 3) {
					temp[r][c] = 0;
					kill++;
				}else if(temp[r][c] == 1) {
					temp[r][c] = 0;
					if(isIn(r+1, c)) {
						temp[r+1][c] = 1;
					}
				}
			}
		}
		return kill;
	}

	private static void bfs(int start) {
		isVisited = new boolean[N][M];
		Queue<Node> queue = new LinkedList<>();
		queue.offer(new Node(N, start, 0));
//		isVisited(N,start) // 이거하면 범위 초과 에러날듯?
		
		while(!queue.isEmpty()) {
			Node front = queue.poll();
			if(isIn(front.r, front.c) && temp[front.r][front.c] != 0) {
				temp[front.r][front.c] = 3;
				break;
			}
			if(front.d < D) {
				for(int d=0; d<3; d++) {
					int nr = front.r + dr[d];
					int nc = front.c + dc[d];
					if(isIn(nr, nc) && !isVisited[nr][nc]) { // map[nr][nc] 가 뭔진 상관없을듯?
						queue.offer(new Node(nr, nc, front.d+1));
						isVisited[nr][nc] = true;
					}
				}
			}
		}
	}
	
	static class Node{
		int r;
		int c;
		int d;
		public Node(int r, int c, int d) {
			super();
			this.r = r;
			this.c = c;
			this.d = d;
		}
		@Override
		public String toString() {
			return "Node [r=" + r + ", c=" + c + ", d=" + d + "]";
		}
	}
	
	static int dr[] = {0,-1,0}; // 왼, 위, 오
	static int dc[] = {-1,0,1};
	
	static boolean isIn(int r, int c) {
		return (r>=0 && c>=0 && r<N && c<M);
	}

	static String src =
			"6 5 2\r\n"
			+ "1 0 1 0 1\r\n"
			+ "0 1 0 1 0\r\n"
			+ "1 1 0 0 0\r\n"
			+ "0 0 0 1 1\r\n"
			+ "1 1 0 1 1\r\n"
			+ "0 0 1 0 0";
}

 

리얼 후기

 

뭔짓을 해도 결국 이차원 배열만한게 없나보다. 더 줄일수도 있겠지만 슬슬 질려서 다음 문제로 넘어가야겠다.