[BOJ] 백준 17135. 캐슬 디펜스

문제

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

 

 

---

풀이

전형적인 삼성 코테의 빡 구현 문제입니다.

 

 구현만 충실히 수행하면 되었는데, 삼성 SW 역량 문제의 구현 파트를 풀 때마다 느끼는 것은, 구현 시 중복된 데이터가 처리되는 것을 꼼꼼하게 잘 피해야하는 것 같습니다. 

 

 위 문제에서도 적의 수를 세는 부분이나, 적이 이동할 때 등등 for문을 돌며 배열에서만 구현을 처리하려하면 중복되는 데이터로 인해 원하는 결과가 나오지 않습니다. 그래서 저는 list 자료 구조를 따로 선언해 데이터를 저장하고, 후 처리를 해주는 식으로 풀이를 진행했습니다. 

 

 자세한 풀이 과정은 주석으로 대체했습니다.

 

아래는 소스 코드입니다.

---

소스 코드

import java.util.*;

public class B17135_캐슬디펜스 {

    static int N,M,D;
    static int[][] map;
    static int[][] cloneMap;
    static boolean[] visited;
    static int[] selected = new int[3];
    static ArrayList<int[]> enemyList;
    static int cnt;
    static int max = -1;
    static Scanner sc = new Scanner(System.in);

    public static void main(String[] args) {
        input();
        selectArcher(0,0);
        System.out.println(max);
    }

    static void selectArcher(int depth, int idx){ // 궁수 위치 구하기
        if(depth == 3){
            cloneMap = new int[N][M];
            for(int r = 0; r<N;r++){  //궁수의 위치마다 적의 위치는 제자리에 있어야함으로
                for(int c=0;c<M;c++){ // 복제해서 사용한다
                    cloneMap[r][c] = map[r][c];
                }
            }
            playGame();
            max = Math.max(cnt,max);
        }
        else{
            for(int i = idx; i<M;i++){
                if(!visited[i]) {
                    visited[i] = true;
                    selected[depth] = i;
                    selectArcher(depth+1, i+1);
                    visited[i] = false;
                }
            }
        }
    }

    static void playGame(){ // 게임 시작
        cnt = 0;
        while(!isEnemyEmpty()){ // 적이 비어있지않다면
            destroyEnemy(); //적 제거
            enemyMove(); // 적 이동
        }

    }

    static void destroyEnemy(){ // 적 제거
        enemyList = new ArrayList<>(); // 적 위치 담을 배열
        for(int i = 0;i<3;i++) {
            selectEnemy(selected[i]);
        }
        for(int[] enemy:enemyList){
            if(cloneMap[enemy[0]][enemy[1]]==1) { //적이 이미 제거되었을수도 있어 체크필요
                cloneMap[enemy[0]][enemy[1]] = 0;
                cnt++;
            }
        }
    }
    
    static void selectEnemy(int archerCol){ // 궁수 당 한명씩 타겟팅
        int targetR = -1;
        int targetC = -1;
        int min = 987654321;

        for(int c=0;c<M;c++){ //c부터 돈 이유는 왼쪽 적이 우선시 되기 때문.
            for(int r = 0; r<N;r++){
                if(cloneMap[r][c] == 1){
                    int distance = getDistance(r,c,archerCol);
                    if(distance<=D&&distance<min){ // 최소 하나만 구한다
                        targetR = r;
                        targetC = c;
                        min = distance; // 최소 값 업데이트
                    }
                }
            }
        }
        if(targetR!=-1) enemyList.add(new int[]{targetR,targetC}); // 적이 없으면 넘기기
    }

    static int getDistance(int r, int c, int archerCol){ // 적과의 거리 구하기
        return Math.abs(r-N)+Math.abs((c-archerCol));
    }
    
    static void enemyMove(){ // 적 이동
        ArrayList<int[]> list = new ArrayList<>(); // 적들을 임시로 담을 리스트
        for(int r = 0; r<N;r++){
            for(int c=0;c<M;c++){
                if(cloneMap[r][c] == 1){
                    list.add(new int[]{r+1,c}); //적이라면 리스트에 담고 없애준다.
                    cloneMap[r][c] = 0;
                }
            }
        }
        for(int[] movePos:list){ //리스트에 담긴 적을 이동시켜준다
            int r = movePos[0];
            int c = movePos[1];
            if(r>=N) continue; //범위 넘어가면 그대로 적 제거
            cloneMap[r][c] = 1;
        }
    }
    
    static boolean isEnemyEmpty(){
        for(int r = 0; r<N;r++){
            for(int c=0;c<M;c++){
                if(cloneMap[r][c] == 1) return false;
            }
        }
        return true;
    }

    static void input(){
        N = sc.nextInt();
        M = sc.nextInt();
        D = sc.nextInt();
        map = new int[N][M];
        visited = new boolean[M];
        for(int r = 0; r<N;r++){
            for(int c=0;c<M;c++){
                map[r][c] = sc.nextInt();
            }
        }
    }
}