[백준/boj] 17135: 캐슬 디펜스 (Java) / 조합 / 구현

문제

17135번: 캐슬 디펜스

풀이 1

메모리와 시간이 좀 더 나은 버전

import java.util.*;
import java.io.*;

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int N, M, D;
	static int[][] castle;
	static int[][] castleClone;
	static int score = 0;
	static int[][] playerPos = new int[3][2];
	static int[] pos1 = new int[2], pos2 = new int[2], pos3 = new int[2];

	public static void main(String[] args) throws Exception {
		input();
		combination(0, 0, new int[3]);
		System.out.println(score);
	}

	private static void combination(int cnt, int start, int[] player) {
		if (cnt == 3) {
			int i = 0;
			for (int n : player) {
				playerPos[i][0] = N;
				playerPos[i++][1] = n;
			}
			cloneMap();
			int newScore = game();
			score = Math.max(score, newScore);
			return;
		}

		for (int i = start; i < M; i++) {
			player[cnt] = i;
			combination(cnt + 1, i + 1, player);
		}
	}
    
	private static void cloneMap() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				castle[i][j] = 0;
				if (castleClone[i][j] == 1) {
					castle[i][j] = 1;
				}
			}
		}
	}
    
	private static int game() {
		int newScore = 0;
		int count = 0;
		int num1 = Integer.MAX_VALUE, num2 = Integer.MAX_VALUE, num3 = Integer.MAX_VALUE;

		pos1[0] = 0;
		pos1[1] = 0;
		pos2[0] = 0;
		pos2[1] = 0;
		pos3[0] = 0;
		pos3[1] = 0;

		while (count < N) {
			int limit = N-D >= 0? N-D : 0;
			for (int j = M - 1; j >= 0; j--) { // 오른쪽부터 왼쪽으로 
            								// (최종적으로 최소 거리의 적들 중, 제일 왼쪽에 위치한 적의 좌표가 담길것이다.)
				for (int i = N - 1; i >= limit; i--) { // 성과 제일 가까운 행(N-1)부터 limit행까지

					if (castle[i][j] == 1) {
						int value = Math.abs(playerPos[0][0] - i) + Math.abs(playerPos[0][1] - j);
						if (D >= value) {
							if (value <= num1) {
								num1 = value;
								pos1[0] = i;
								pos1[1] = j;
							}
						}

						value = Math.abs(playerPos[1][0] - i) + Math.abs(playerPos[1][1] - j);
						if (D >= value) {
							if (value <= num2) {
								num2 = value;
								pos2[0] = i;
								pos2[1] = j;
							}
						}

						value = Math.abs(playerPos[2][0] - i) + Math.abs(playerPos[2][1] - j);
						if (D >= value) {
							if (value <= num3) {
								num3 = value;
								pos3[0] = i;
								pos3[1] = j;
							}
						}

					}
				}
			}

			if (pos1[0] == 0 && pos1[1] == 0) {

			} else {
				if (castle[pos1[0]][pos1[1]] != 0) {
					newScore++;
					castle[pos1[0]][pos1[1]] = 0;
				}
			}

			if (pos2[0] == 0 && pos2[1] == 0) {

			} else {
				if (castle[pos2[0]][pos2[1]] != 0) {
					newScore++;
					castle[pos2[0]][pos2[1]] = 0;
				}
			}

			if (pos3[0] == 0 && pos3[1] == 0) {

			} else {
				if (castle[pos3[0]][pos3[1]] != 0) {
					newScore++;
					castle[pos3[0]][pos3[1]] = 0;
				}
			}

			pos1[0] = 0;
			pos1[1] = 0;
			pos2[0] = 0;
			pos2[1] = 0;
			pos3[0] = 0;
			pos3[1] = 0;
			num1 = Integer.MAX_VALUE;
			num2 = Integer.MAX_VALUE;
			num3 = Integer.MAX_VALUE;

			move();
			count++;
		}

		return newScore;
	}

	private static void move() {
		for (int i = N - 1; i > 0; i--) {
			for (int j = 0; j < M; j++) {
				if (castle[i - 1][j] == 1) {
					castle[i][j] = 1;
				} else {
					castle[i][j] = 0;
				}
			}
		}

		for (int i = 0; i < M; i++) {
			castle[0][i] = 0;
		}
	}

	private static void input() throws Exception {
		st = new StringTokenizer(br.readLine());
		N = stoi(st.nextToken());
		M = stoi(st.nextToken());
		D = stoi(st.nextToken());
		castle = new int[N][M];
		castleClone = new int[N][M];

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				int input = stoi(st.nextToken());
				castle[i][j] = input;
				castleClone[i][j] = input;
			}
		}
	}

	private static int stoi(String input) {
		return Integer.parseInt(input);
	}
}

 

함수 설명

• combination(int cnt, int start, int[] player): N행에 위치할 궁수들의 열 값을 구하는 조합. 조합이 하나 생성될 때마다 게임을 실행한다.(game) 
• cloneMap(): 궁수 위치 조합마다 게임을 진행하고 나면 castle이 전부 0으로 재할당되는데 이를 다시 원래 맵으로 돌리기 위한 함수이다.
• game(): 궁수 위치 조합이 나올때마다 game을 진행한다.
  • newScore: 해당 게임의 죽인 적의 수
  • count: N-1까지 1씩 증가하는 변수. 0행에 위치한 적군이 N 행에 올때까지 게임을 진행하기 위해 생성 (while(count <N)) 
  • num1, num2, num3: 적과 궁수의 최소 거리를 담는 int 변수 ( 3명의 궁수이기 때문에 num3 까지 생성) 계속 최솟값으로 갱신되어야하기 때문에 Integer.MAX_VALUE; 로 초기화했다.
  • pos1 ,pos2, pos3: 적과 궁수가 최소 거리일 때 적의 좌표를 담는 int[2] 배열. 예를 들어, 궁수1과의 거리 최솟 값이 D이하를 만족하는 적들 중 가장 왼쪽에 위치하는 적의 x좌표는 pos1[0]에 담기고 적의 y좌표는 pos1[1] 에 담긴다.
  • limit: 나는 적들의 거리를 계산할 때, N-1 행 부터 N-D 행까지 거슬러 올라갔다. 테스트 케이스 중에 D가 N보다 큰 경우가 있을 수 있기 때문에 그런경우 0으로 limit을 설정해 0행까지 거슬러 올라가며 거리를 계산하도록 했다.
  • castle[i][j] ==1 이라는 것은 적이 위치한다는 것을 의미한다. 이때 모든 궁수와 거리값을 계산한다.
    1. 궁수1 부터 적과의 거리를 계산한다. 그 거리 값이 D(공격 거리) 이하이면서, castle에 위치한 적들 중 궁수1과 가장 가깝다면num1을 갱신하고, pos 배열을 그 적의 좌표로 할당한다. 오른쪽열에서 왼쪽열로 비교하면서 작거나 같을때 갱신하기 때문에 같은 거리를 갖는다면 가장 왼쪽의 적을 죽인다 는 조건을 만족할 수 있다.
    2. 궁수2, 3도 똑같이 진행
    3. 이중 포문이 끝나 모든 궁수에게 죽일 적이 정해졌다. 이때 pos 배열이 0,0 라는 것은 공격거리 D이하의 거리에 적이 없는 것을 의미하므로 아무것도 하지 않는다.
    4. 죽일 적이 있다면 그 자리(castle[pos[0]][pos[1]])가 1인지 0인지 확인한다. 0이라는 것은 이미 앞선 궁수가 죽였음을 의미한다. ( 같은 적을 동시에 죽일 수 있다. ) 같은 적의 정보를 가질 순 있지만 2번 죽일 순 없으므로 적의 자리가 1일 때만 newScore를 1 UP 한다.
    5. 다 죽였으면 pos 와 num을 다시 초기화한다.
• move(): 적군들이 성쪽으로 내려오는 과정을 구현하는 함수이다. N-1 행부터 이전행의 값들을 넣으면 된다. (주의 ! castle[i] = castle[i-1] 로 하는 경우 얕은 복사가 일어나 castle[i] 가 바뀌면 castle[i-1] 도 바뀌는 현상이 일어난다. )
• input(): 성의 정보를 받아온다. (castleClone은 2차원 배열의 깊은 복사를 위해 생성했다.)
• stoi(String input): String을 int로 형변환

풀이 2

class 생성 및 for문을 활용해 코드를 단순화한 버전

 

import java.util.*;
import java.io.*;

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int N, M, D;
	static int[][] castle;
	static int[][] castleClone;
	static int score = 0;
	static int[][] playerPos = new int[3][2];
	static int[] pos1 = new int[2], pos2 = new int[2], pos3 = new int[2];
	static Player[] player = new Player[3];

	public static class Player {
		int x;
		int y;

		public Player(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}

	public static void main(String[] args) throws Exception {
		input();
		combination(0, 0, new int[3]);
		System.out.println(score);
	}

	private static void combination(int cnt, int start, int[] player) { 
		if (cnt == 3) {
			int i = 0;
			for (int n : player) {
				playerPos[i][0] = N;
				playerPos[i++][1] = n;
			}
			cloneMap();
			int newScore = game();
			score = Math.max(score, newScore);
			return;
		}

		for (int i = start; i < M; i++) {
			player[cnt] = i;
			combination(cnt + 1, i + 1, player);
		}
	}

	private static int game() {
		int newScore = 0;
		int count = 0;
		int[] nums = new int[3];

		for (int i = 0; i < 3; i++) {
			player[i] = new Player(0, 0);
			nums[i] = Integer.MAX_VALUE;
		}

		int limit = N - D >= 0 ? N - D : 0;
		while (count < N) {
			for (int j = M - 1; j >= 0; j--) {
				for (int i = N - 1; i >= limit; i--) {
					for (int n = 0; n < 3; n++) {
						if (castle[i][j] == 1) {
							int value = Math.abs(playerPos[n][0] - i) + Math.abs(playerPos[n][1] - j);
							if (D >= value) {
								if (value <= nums[n]) {
									nums[n] = value;
									player[n].x = i;
									player[n].y = j;
								}
							}

						}
					}
				}
			}

			for (int n = 0; n < 3; n++) {
				if (player[n].x == 0 && player[n].y == 0) {

				} else {
					if (castle[player[n].x][player[n].y] != 0) {
						newScore++;
						castle[player[n].x][player[n].y] = 0;
					}
				}
				player[n] = new Player(0, 0);
				nums[n] = Integer.MAX_VALUE;
			}
			move();
			count++;
		}

		return newScore;
	}

	private static void move() {
		for (int i = N - 1; i > 0; i--) {
			for (int j = 0; j < M; j++) {
				if (castle[i - 1][j] == 1) {
					castle[i][j] = 1;
				} else {
					castle[i][j] = 0;
				}
			}
		}

		for (int i = 0; i < M; i++) {
			castle[0][i] = 0;
		}
	}

	private static void cloneMap() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				castle[i][j] = 0;
				if (castleClone[i][j] == 1) {
					castle[i][j] = 1;
				}
			}
		}
	}

	private static void input() throws Exception {
		st = new StringTokenizer(br.readLine());
		N = stoi(st.nextToken());
		M = stoi(st.nextToken());
		D = stoi(st.nextToken());
		castle = new int[N][M];
		castleClone = new int[N][M];

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				int input = stoi(st.nextToken());
				castle[i][j] = input;
				castleClone[i][j] = input;
			}
		}
	}

	private static int stoi(String input) {
		return Integer.parseInt(input);
	}
}

flow는 동일하며 game 함수와 Player Class를 가지는 점이 다르다.

함수 설명

• game(): 궁수 위치 조합이 나올때마다 game을 진행한다.
  • newScore: 해당 게임의 죽인 적의 수
  • count: N-1까지 1씩 증가하는 변수. 0행에 위치한 적군이 N 행에 올때까지 게임을 진행하기 위해 생성 (while(count <N)) 
  • nums: 적과 궁수의 최소 거리를 담는 int[] 배열 ( 3명의 궁수이기 때문에 길이 3을 갖는다.) 계속 최솟값으로 갱신되어야하기 때문에 Integer.MAX_VALUE; 로 초기화했다. (풀이1의 num과 동일 역할)
  • player: x,y 좌표를 가지는 Player 클래스 객체 3개를 담는 Player[3] 배열 (풀이1의 pos 와 동일 역할)
  • 같은 코드가 3번 반복되는 것을 for(int n=0; n<3; n++) 안에 한 코드로 작성해 간소화했다.

 

위가 풀이2 , 아래가 풀이1