백준 17135 <캐슬 디펜스>

조합으로 3명의 궁수를 배치하고 나서 게임을 진행하는 시뮬레이션 문제!

 

문제를 잘읽어보는게 포인트인 문제이다.

 

문제 풀이

 

1. M개중에 3개의 궁수위치를 조합으로 선택한다.
2. 각각의 궁수 위치에서 D 이하이면서 가장 가깝고 왼쪽에 있는 적을 선택한다.
3. 적은 한칸씩 당겨준다.

여기서 주의할 점은 같은 적을 때릴 경우가 있다는 것이다. 

조합으로 궁수의 위치를 선택한다

 

D거리 이하중 가장 가깝고 왼쪽에 있는 것 선택!!! 

그 이후 적을 죽이고 맵을 당겨오는 과정

 

여기서 생각해야 할 점 하나 더!

 

조합으로 선택한 후 적을 죽이고 맵을 당겨오는 과정이 있기 때문에 map을 복사해서 사용!

 

전체 코드

import java.awt.Point;
import 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 Point num[];
	static int n, m, d, max;
	static int map[][], map2[][];

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		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];
		map2 = new int[n][m];
		num = new Point[3];
		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());
			}
		}
		find(0, 0);
		System.out.println(max);
	}

	private static void find(int i, int j) {
		// TODO Auto-generated method stub
		if (j == 3) {
			reset();
			attack();
			return;
		}
		for (int k = i; k < m; k++) {
			num[j] = new Point(n, k);
			find(k + 1, j + 1);
		}
	}

	private static void reset() {
		// TODO Auto-generated method stub
		for (int i = 0; i <n; i++) {
			for (int j = 0; j < m; j++) {
				map2[i][j] = map[i][j];
			}
		}
	}

	private static void attack() {
		// TODO Auto-generated method stub
		int count = 0;
		for (int i = 0; i < n; i++) {
			Point at[] = new Point[3];
			int di[] = { d + 1, d + 1, d + 1 };
			for (int j = 0; j < 3; j++) {//궁수들 움직이기
				for (int w = 0; w < m; w++) {
					for (int h = n - 1; h >= 0; h--) {
						if (map2[h][w] == 1 &&
                            (Math.abs(num[j].x - h) + Math.abs(num[j].y - w)) < di[j]) {
							di[j] = Math.abs(num[j].x - h) + Math.abs(num[j].y - w);
							at[j] = new Point(h, w);
						}
					}
				}
			} // 가장 가까운 곳 찾기
			for (int j = 0; j < 3; j++) {
				if (at[j] != null) {
					if (map2[at[j].x][at[j].y] == 1) {
						count++;
					}
					map2[at[j].x][at[j].y] = 0;
				}
			} // 적 맞춘 카운트 세주기
			for (int h = n - 2; h >= 0; h--) {
				for (int w = 0; w < m; w++) {
					map2[h + 1][w] = map2[h][w];
				}
			} // 이동
			for (int w = 0; w < m; w++) {
				map2[0][w] =0;
			}
		}
		if(max< count)
			max =count;
	}
}