[백준] code.plus(브루트 포스 Part 1,JAVA)17135번, 캐슬 디펜스

문제 링크

17135번: 캐슬 디펜스

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심은

 

1. 각 성은 N+1에 열 모든 행에 존재하며 3명의 궁수가 배치될 수 있습니다.

2. 궁수는 D거리에 존재하는 적 중 우선순위에 맞게 동시에 공격합니다. 

3. 궁수가 공격을 한 뒤에 적은 한 칸씩 내려옵니다.

4. 적은 성에 도착하거나 공격에 맞으면 제외됩니다.

5. 적이 모두 제외되었을 때 진행이 종료됩니다.

6. 적을 공격해서 제외하는 횟수가 가장 많은 경우를 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력되는 정보들을 저장합니다.

 

2. 궁수를 배치하는 모든 경우에서 시뮬레이션을 진행합니다.

 

3. 모든 시뮬레이션 종료 후 가장 공격 제외하는 횟수를 많은 값을 결과로 출력합니다.

 

시뮬레이션.

 

1. 궁수 배치!

 

N+1열에 모든 행에서 3곳에 성을 선택하여 배치합니다.

 

2. 궁수  동시 공격!

 

BFS를 통해서 우선순위에 맞게 가장 가까운 적을 찾습니다.

 

3. 적 이동!

 

존재하는 적들 한 칸씩 움직이기!

 

4. 2~3을 공간에 적이 존재하지 않을 때까지 반복합니다.

 

※공격할 위치를 BFS탐색으로 진행하는 이유

 

거리를 구하는 공식이 |r₁ - r₂| + |c₁ - c₂|이기 때문에

임의의 위치에서  거리를 표현해보면

2	1	2	3
1	임의의 위치(2, 1)	1	2
2	1	2	3
3	2	3	4

90도로 상하좌우 이동하는 것으로 거리가 1씩 증가하기 때문에 BFS를 이용해서 구현하였습니다.

 

예제입력 3.

 

1. 입력되는 정보들을 저장합니다.

 

N = 5, M = 5, D = 2

0	0	0	0	0
0	0	0	0	0
0	0	0	0	0
1	1	1	1	1
0	0	0	0	0

 

2. 궁수를 배치하는 모든 경우에서 시뮬레이션을 진행합니다.

 

※궁수를 배치하는 경우는 여러가지이지만 1개의 경우만 시뮬레이션 진행하는 것을 보여드리겠습니다.

 

1. 궁수 배치(0, 2, 4)

 

2. 궁수 동시 공격!

 

0	0	0	0	0
0	0	0	0	0
0	0	0	0	0
X(공격1)	1	X(공격2)	1	X(공격3)
0	0	0	0	0
궁수1	-	궁수2	-	궁수3

 

3. 적 이동!

0	0	0	0	0
0	0	0	0	0
0	0	0	0	0
0	0	0	0	0
0	1	0	1	0
궁수	-	궁수	-	궁수

 

4. 적이 존재하기 때문에 다시 반복!

 

2. 궁수 동시 공격!

0	0	0	0	0
0	0	0	0	0
0	0	0	0	0
0	0	0	0	0
0	X(공격1,공격2)	0	X(공격3)	0
궁수1	-	궁수2	-	궁수3

 

3. 적 이동!

0	0	0	0	0
0	0	0	0	0
0	0	0	0	0
0	0	0	0	0
0	0	0	0	0
궁수	-	궁수	-	궁수

 

4. 적이 존재하지 않기 때문에 시뮬레이션 종료

 

적을 제외한 횟수 : 5번

 

3. 모든 시뮬레이션 종료 후 가장 공격 제외하는 횟수를 많은 값을 결과로 출력합니다.

 

적을 제외한 최대값 5을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 이용하여 입력값을 띄어쓰기 기준으로 나누었습니다.
• search함수를 궁수 배치의 모든 경우를 시뮬레이션을 진행합니다.
• 모든 시뮬레이션 종료 후 적을 제외한 공격 최대 횟수를 BufferedWriter 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• search함수는 재귀를 통해서 궁수를 배치하는 모든 경우를 탐색하여 시뮬레이션을 진행합니다.
• simulation함수는 배치된 궁수들이 공격 및 적의 이동에 대한 시뮬레이션을 진행합니다.
• attack함수는 BFS를 통해 궁수들이 적을 공격할 위치를 구합니다.
• enemyMove함수는 적들이 한 칸씩 이동을 진행합니다.
• inSpace함수는 이동하려는 칸이 공간이 존재하는지 확인합니다.
• rollBack함수는 원래 공간의 상태로 복구를 진행합니다.

 

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

public class Main {
    //시뮬레이션 도중 위치 정보 클래스
    static class info implements Comparable<info> {
        int x, y, d;

        public info(int x, int y, int d) {
            this.x = x;
            this.y = y;
            this.d = d;
        }
        public info(int x, int y) {
            this.x = x;
            this.y = y;
            this.d = 0;
        }
        //거리 오름차순, x값 오름차순
        @Override
        public int compareTo(info o) {
            if(this.d==o.d)
                return this.x - o.x;
            else
                return this.d - o.d;
        }
    }

    static int N, M, D, attackSize = 0, answer = 0;
    static int[][] map, temp;
    static int[] select = new int[3];	//선택한 궁수들 저장 배열
    static info[] attackPosition = new info[3];	//궁수들 공격할 위치 저장 배열
    static int[] dx = {-1, 0, 1};	//좌상우 x변경값
    static int[] dy = {0, -1, 0};	//좌상우 y변경값

    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        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+1][M];
        temp = new int[N+1][M];
        //입력값 저장
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < M; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                temp[i][j] = map[i][j];
                //적 이동 반복할 횟수 저장
                if (map[i][j] == 1 && attackSize == 0)
                    attackSize = N - i + 1;
            }
        }
        //궁수 배치 모든 경우 탐색
        for (int i = 0; i < M; i++) {
            select[0] = i;
            search(1, i);
        }
        bw.write(answer + "");	//적 제외한 최대값 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //궁수를 배치하는 모든 경우 및 시뮬레이션 진행함수 호출
    static void search(int depth, int index) {
        if (depth == 3) {
            simulation();	//시뮬레이션 호출
            rollBack();		//원상태 복구
            return;
        }
        //궁수 배치 탐색
        for (int i = index + 1; i < M; i++) {
            select[depth] = i;
            search(depth + 1, i);
        }
    }
    //시뮬레이션 진행하는 함수
    static void simulation() {
        int result = 0;
        int size = attackSize;
        while (size > 0) {
            //궁수 공격 위치 구하기!
            for (int i = 0; i < 3; i++)
                attack(select[i], i);
            //궁수 공격 진행
            for (int i = 0; i < 3; i++) {
                if (map[attackPosition[i].y][attackPosition[i].x] == 1) {
                    map[attackPosition[i].y][attackPosition[i].x] = 0;
                    result++;
                }
            }
            enemyMove();	//적 이동
            size--;
        }
        answer = Math.max(answer, result);	//최대값인지 비교하기
    }
    //궁수가 공격할 위치 구하는 BFS함수
    static void attack(int col, int index){
        PriorityQueue<info> q = new PriorityQueue<>();
        boolean[][] visited = new boolean[N+1][M];
        visited[N][col] = true;
        q.add(new info(col, N, 1));
        while(!q.isEmpty()){
            info cur = q.poll();
            //가장 가까운 적에 도착시.
            if(cur.d<=D && map[cur.y][cur.x]==1){
                attackPosition[index] = new info(cur.x, cur.y);
                return;
            }
            if(cur.d==D)		//사정거리가 더 갈 수 없을 때
                continue;
            //좌상우 탐색
            for(int i=0;i<3;i++){
                int tempX = cur.x + dx[i];
                int tempY = cur.y + dy[i];
                if(inSpace(tempX,tempY) && !visited[tempY][tempX]){
                    visited[tempY][tempX] = true;
                    q.add(new info(tempX,tempY,cur.d+1));
                }
            }
        }
        attackPosition[index] = new info(0, 0);	//공격할 적이 없을 때
    }
    //적 이동하는 함수
    static void enemyMove(){
        for(int i=N;i>0;i--){
            for(int j=0;j<M;j++)
                map[i][j] = map[i-1][j];
        }
    }
    //이동시 공간에 존재하는지 확인하는 함수
    static boolean inSpace(int x, int y){
        if(x>=0 && y>=0 && x<M && y<=N)
            return true;
        return false;
    }
    //기존 공간에 상태로 되돌리는 함수
    static void rollBack(){
        for(int i=0;i<=N;i++)
            for(int j=0;j<M;j++)
                map[i][j] = temp[i][j];
    }
}