[알고리즘] 캐슬 디펜스 (백준 17135번)

17135번: 캐슬 디펜스

 브루트 포스 + 시뮬레이션 문제이다. 문제의 조건을 좀 헷갈리게 해놔서 조건을 잘 파악해서 어떻게 모듈화할지 생각해야 한다.

 

Solution

1. dfs (백트랙킹 함수)

	public static void dfs(int index, ArrayList<Position> archers)
	{
		if(archers.size() == 3)
		{
			//시뮬레이션
			int sim_map[][] = new int[N][M];

			for(int i = 0;i < N;i++)
				sim_map[i] = map[i].clone();

			ArrayList<Position> enemyList = new ArrayList<>();

			int count = 0;

			//모든 맵이 0될 때 까지
			while(!isFinish(sim_map))
			{
				//죽일 적들 골라오기
				for(int i = 0;i < 3;i++)
				{
					Position enemy = selectEnemy(sim_map, archers.get(i).x, archers.get(i).y);

					//죽일 수 있는 적이 없음
					if(enemy.x == archers.get(i).x && enemy.y == archers.get(i).y)
						continue;

					//중복 아닌 것만
					if(!enemyList.contains(enemy))
						enemyList.add(enemy);
				}

				count += enemyList.size();
				killEnemy(enemyList, sim_map);
				//System.out.println(Arrays.deepToString(sim_map));
				moveEnemy(sim_map);

			}
			//System.out.println();
			max = Math.max(max, count);
		}
		else
		{
			for(int j = index; j < M;j++)
			{
				archers.add(new Position(N, j));
				dfs(j + 1,archers);
				archers.remove(archers.size() - 1);
			}
		}
	}

1. archer 3명의 위치를 다 정할 때까지 탐색한다.
2. archer 3명의 위치를 정하면 시뮬레이션을 시작한다.
3. archer들이 죽일 적들의 위치를 골라온다.
4. 적을 죽이고 나머지 적들은 맵 밑으로 한칸씩 움직인다.
5. isFinish가 참이면 종료 시킨다.
6. 죽인 적들의 수가 max인지 확인 한다.

 

2. isFinish(종료 여부 판단 함수)

	public static boolean isFinish(int[][] map)
	{
		for(int i = 0;i < N;i++)
		{
			for(int j = 0;j < M;j++)
			{
				if(map[i][j] > 0)
					return false;
			}
		}
		return true;
	}

 

 전체 맵을 탐색하여서 모두가 0이면 참을 반환하여 종료 조건을 만족시킨다.

 

3. selectEnemy(궁수가 죽일 적들 골라오기)

	//가장가까운 적 고르기 -> 없으면 내 위치 그냥 반환
	public static Position selectEnemy(int map[][], int x, int y)
	{
		int min = D;

		PriorityQueue<Position> queue = new PriorityQueue<Position>((o1, o2) -> {
			int dis1 = Math.abs(x - o1.x) + Math.abs(y - o1.y);
			int dis2 = Math.abs(x - o2.x) + Math.abs(y - o2.y);

			if(dis1 == dis2)
				return o1.y - o2.y;
			else
				return dis1 - dis2;
		});
		for(int i = N - 1;i >= 0;i--)
		{
			for(int j = 0;j < M;j++)
			{
				int dis = Math.abs(x - i) + Math.abs(y - j);
				if(map[i][j] == 1 && dis  <= min)
				{
					min = dis;
					queue.offer(new Position(i,j));
				}
			}
		}

		if(queue.isEmpty())
			return new Position(x, y);
		return queue.poll();
	}

1. 우선순위 큐를 만들어서 거리가 가장 가까운 것, 거리가 같다면 가장 왼쪽에 있는 것을 순서로 오름차순 정렬한다.
2. 최초의 min 값을 D로 두고 min보다 작다면 queue에 추가한다.
3. 큐가 비어있다면 자기 자신 위치를 반환한다.
4. 큐가 안 비었다면 맨 앞에 있는 요소를 반환한다. (가장 거리가 짧고 왼쪽에 있는 적)

 

4. killEnemy(적 죽이기)

	public static void killEnemy(ArrayList<Position> enemyList, int[][] map)
	{
		for(int i = 0;i < enemyList.size();i++)
		{
			Position now = enemyList.get(i);
			map[now.x][now.y] = 0;
		}
		enemyList.clear();
	}

 리스트에 있는 위치들을 불러와서 0으로 만들어서 적을 죽인다.

 

5. moveEnemy(적 움직이기)

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

 해당 턴이 종료되기 직전에 적들을 한 칸씩 밑으로 움직인다.

 

 

전체 코드

import javafx.geometry.Pos;

import javax.swing.*;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;
import java.util.stream.IntStream;

public class Main {

	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

	static int N, M, D;
	static int map[][];
	static int max = 0;

	public static void solution() throws Exception
	{
		String[] list = br.readLine().split(" ");
		N = Integer.parseInt(list[0]);
		M = Integer.parseInt(list[1]);
		D = Integer.parseInt(list[2]);

		map = new int[N][M];
		for(int i = 0;i < N;i++)
		{
			list = br.readLine().split(" ");
			for(int j = 0;j < M;j++)
				map[i][j] = Integer.parseInt(list[j]);
		}

		dfs(0, new ArrayList<>());
		bw.write(max+"");


	}

	public static void dfs(int index, ArrayList<Position> archers)
	{
		if(archers.size() == 3)
		{
			//시뮬레이션
			int sim_map[][] = new int[N][M];

			for(int i = 0;i < N;i++)
				sim_map[i] = map[i].clone();

			ArrayList<Position> enemyList = new ArrayList<>();

			int count = 0;

			//모든 맵이 0될 때 까지
			while(!isFinish(sim_map))
			{
				//죽일 적들 골라오기
				for(int i = 0;i < 3;i++)
				{
					Position enemy = selectEnemy(sim_map, archers.get(i).x, archers.get(i).y);

					//죽일 수 있는 적이 없음
					if(enemy.x == archers.get(i).x && enemy.y == archers.get(i).y)
						continue;

					//중복 아닌 것만
					if(!enemyList.contains(enemy))
						enemyList.add(enemy);
				}

				count += enemyList.size();
				killEnemy(enemyList, sim_map);
				//System.out.println(Arrays.deepToString(sim_map));
				moveEnemy(sim_map);

			}
			//System.out.println();
			max = Math.max(max, count);
		}
		else
		{
			for(int j = index; j < M;j++)
			{
				archers.add(new Position(N, j));
				dfs(j + 1,archers);
				archers.remove(archers.size() - 1);
			}
		}
	}

	//가장가까운 적 고르기 -> 없으면 내 위치 그냥 반환
	public static Position selectEnemy(int map[][], int x, int y)
	{
		int min = D;

		PriorityQueue<Position> queue = new PriorityQueue<Position>((o1, o2) -> {
			int dis1 = Math.abs(x - o1.x) + Math.abs(y - o1.y);
			int dis2 = Math.abs(x - o2.x) + Math.abs(y - o2.y);

			if(dis1 == dis2)
				return o1.y - o2.y;
			else
				return dis1 - dis2;
		});
		for(int i = N - 1;i >= 0;i--)
		{
			for(int j = 0;j < M;j++)
			{
				int dis = Math.abs(x - i) + Math.abs(y - j);
				if(map[i][j] == 1 && dis  <= min)
				{
					min = dis;
					queue.offer(new Position(i,j));
				}
			}
		}

		if(queue.isEmpty())
			return new Position(x, y);
		return queue.poll();
	}

	public static void killEnemy(ArrayList<Position> enemyList, int[][] map)
	{
		for(int i = 0;i < enemyList.size();i++)
		{
			Position now = enemyList.get(i);
			map[now.x][now.y] = 0;
		}
		enemyList.clear();
	}

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

	public static boolean isFinish(int[][] map)
	{
		for(int i = 0;i < N;i++)
		{
			for(int j = 0;j < M;j++)
			{
				if(map[i][j] > 0)
					return false;
			}
		}
		return true;
	}

	static class Position{
		int x, y;

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

		@Override
		public boolean equals(Object obj) {
			Position other=  (Position) obj;
			return other.x == x && other.y == y;
		}
	}


	public static void main(String[] args) {
		try
		{
			//solution();
			String 박준현 = "박준현";
			System.out.println(박준현);
			bw.close();
			br.close();
		}
		catch (Exception e)
		{
			e.printStackTrace();
		}
	}

}