알고리즘

[코드트리] 포탑 부수기 - 삼성SW역량테스트 기출문제

영리제리 2024. 7. 11. 17:27

 

일단 이 문제는요~ 쉬운데 어렵고 어려운데 쉬운 문제에요 ^^ 

깜찍이로 마음의 안정부터하고 시작~

할 수 있지 그렇지?

 

문제 설명

문제 링크 (아래 사진 클릭)

[codetree] 포탑 부수기

 

요약

- NxM 크기의 격자에서 K번의 공격을 진행 

- 다음의 4가지 순서를 반복 (*살아남은 포탑의 수가 1개 이하면 즉시 종료)

1. 공격자 선정
    - 공격자 : 공격력이 가장 약한 포탑 => 공격력이 (N+M)만큼 증가함
    - 대상자 : 공격력이 가장 강한 포탑
    * 선정 기준
       - Weak => 가장 약한 포탑
       1. 같은 공격력을 가진 포탑이 여러개면, 가장 최근에 공격한 포탑이 Weak
       2. 가장 최근에 공격한 포탑이 여러개면, (행 + 열)의 합이 가장 큰 포탑이 Weak
       3. (행 + 열)이 같은 포탑이 여러개면, 열 값이 가장 큰 포탑이 Weak
    - 따라서, 대상자는 공격자와 정반대
    
2. 공격자의 공격
    - 레이저 공격: BFS 최단 경로 찾기
    - 포탄 던지기: 8방향 진행
    * 주의: 그래프 범위를 벗어나면 반대방향으로 진행됨.

3. 포탑 부서짐 => 공격력이 0이하가된 포탑은 부서짐.

4. 포탑 정비 => 이전 공격에 상관이 없던 포탑들은 공격력 1 증가

 


풀이

1. 포탑(Potop) 클래스 생성

  • 필요한 필드 : 포탑 공격력, 마지막 공격 시간, x좌표, y좌표, 이전 턴에서 공격에 참여한 여부
  • 포탑의 우선수위 설정 : Comparable 인터페이스 구현
    static class Potop implements Comparable<Potop>{
        int power, lastTime, x, y;
        boolean isPre;
        public Potop(int power, int lastTime, int x, int y, boolean isPre) {
            this.power = power;
            this.lastTime = lastTime;
            this.x = x;
            this.y = y;
            this.isPre = isPre;
        }
        @Override
        public int compareTo(Potop other) {
            // 가장 약한 공격자 뽑기 우선순위
            // 파워는 약한 순
            if(this.power != other.power) return this.power - other.power;
            // 시간은 가장 최근의 시간(큰 순) 
            if(this.lastTime != other.lastTime) return other.lastTime - this.lastTime;
            // (행+열)은 큰 순
            if(this.x+this.y != other.x+other.y) return (other.x+other.y) - (this.x+this.y);
            // 열은 큰 순
            return other.y - this.y;
        }
        public String toString(){
            return "power: "+this.power+", lastTime: "+ this.lastTime + ", isPre: "+this.isPre + ", ("+x+","+y+")";
        }
    }

 

포탑이 영어로 뭔데요,,, ㅎㅎ 살면서 처음 들어봄,,, ㅎㅎ 변수명 짓는건 굉장해 엄청나 중요하지만요 귀엽게 짓는것도 꽤 중요해요 ^^

 

 

2. 공격자(Weak) & 대상자(Strong) 선정 

포탑 클래스를 Comparable의 compareTo() 메소드로 우선수위를 정해 줬으니 정렬로 구할 수 있음.

// liveList : 살아있는 포탑 리스트
Collections.sort(liveList);

 

여담)

저는 처음에 우선순위큐(PriorityQueue)로 하면 되겠다! 생각하고, Comparator로 우선순위를 정해줄려고 했어요^^ 

이렇게요^^

PriorityQueue<Potop> wpq = new PriorityQueue<>(new Comparator<Potop>() {
    @Override
    public int compare(Potop p1, Potop p2) {
    	if(p1.power != p2.power) return p1.power - p2.power;
        if(p1.lastTime != p2.lastTime) return p2.lastTime - p1.lastTime;
        if((p1.x+p1.y) != (p2.x+p2.y)) return (p2.x+p2.y) - (p1.x+p1.y);
        return p2.y - p1.y;
});
PriorityQueue<Potop> spq = new PriorityQueue<>(new Comparator<Potop>() {
    @Override
    public int compare(Potop p1, Potop p2) {
    	if(p1.power != p2.power) return p2.power - p1.power;
        if(p1.lastTime != p2.lastTime) return p1.lastTime - p2.lastTime;
        if((p1.x+p1.y) != (p2.x+p2.y)) return (p1.x+p1.y) - (p2.x+p2.y);
        return p1.y - p2.y;
});

딱 봐도 우선순위큐 두 개나 써야하고 복잡하고 그런거 보이죠~?? 여기선 이 방법이 유리하지 않아요 ㅎㅎ 

그래도 우선순위큐 우선순위 지정하는 방법 언제간 쓸 일이 있으니깐 남겨둘게요 키키

 

3. BFS 최단 경로 찾기

bfs(너비우선탐색)으로 최단 거리를 구할 수 있다는 것은 모두모두 알고있죠?

(현재 노드와 거리가 1인 자식 노드들을 먼저 차례로 탐색하고 큐에 집어 넣은 뒤, 다시 그 자식들의 자식을 차례로 방문하면서, 목적 노드를 찾으면 중단하기 때문에 bfs로 찾은 거리는 최단거리라고 말할 수 있어요!)

그 런 데

"경로"는 어떻게 찾을까요,,,,,

(이 문제에서는 레이저가 훑고 가는 경로에 있는 포탑들도 영향을 받기 때문에 경로를 구해야 함)

결론적으로 말하면 이 부분을 구현하는데 많은 시행착오를 겪었고 결국 방법을 찾아본 뒤 구현하였어요. 

1. Predecessor 리스트 추가
    - 'predecessor'는 선배 노드를 의미
    - 특정 노드에 오기 직전의 노드를 의미
    => 따라서, 특정 노드에 오기 직전의 노드를 기록한다.

2. 백트래킹(Backtracking)으로 경로 찾기
    - 위에서 구한 predecessor 정보를 바탕으로 도착 노드를 시작으로 시작 노드까지의 최단 경로를 구한다.
    - 예) p1 = 도착노드의 predecessor → p2 = p1의 predecessor …

 

        ....
        // 경로의 포탑들
        Pos pre = predecessor[strong.x][strong.y];
        while (true) {
            if (pre.x == weak.x && pre.y == weak.y) {
                break;
            }
            p[pre.x][pre.y].power -= (weak.power / 2);
            p[pre.x][pre.y].isPre = true;

            pre = predecessor[pre.x][pre.y];
        }  
        
        ....

 

 

아! 그리고

그래프를 벗어난 경우 반대편에 영향을 끼치는 것

int nx = (now.x + rdx[i] + N) % N;
int ny = (now.y + rdy[i] + M) % M;

 

이렇게 아주 깔끔하게 범위를 정할 수 있습니다.

이제 코드를 적어볼게요~


코드

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

public class Main {
    
    static int N;
    static int M;
    static int K;
    static Potop[][] p;
    // 레이저 방향: 우하좌상
    static int[] rdx = {0, 1, 0, -1};
    static int[] rdy = {1, 0, -1, 0};
    // 포탄던지기 방향 8방향
    static int[] tdx = {0, 1, 0, -1, -1, -1, 1, 1};
    static int[] tdy = {1, 0, -1, 0, -1, 1, -1, 1};
    static class Potop implements Comparable<Potop>{
        int power, lastTime, x, y;
        boolean isPre;
        public Potop(int power, int lastTime, int x, int y, boolean isPre) {
            this.power = power;
            this.lastTime = lastTime;
            this.x = x;
            this.y = y;
            this.isPre = isPre;
        }
        @Override
        public int compareTo(Potop other) {
            // 가장 약한 공격자 뽑기 우선순위
            // 파워는 약한 순
            if(this.power != other.power) return this.power - other.power;
            // 시간은 가장 최근의 시간(큰 순) 
            if(this.lastTime != other.lastTime) return other.lastTime - this.lastTime;
            // (행+열)은 큰 순
            if(this.x+this.y != other.x+other.y) return (other.x+other.y) - (this.x+this.y);
            // 열은 큰 순
            return other.y - this.y;
        }
        public String toString(){
            return "power: "+this.power+", lastTime: "+ this.lastTime + ", isPre: "+this.isPre + ", ("+x+","+y+")";
        }
    }
    static Potop weak;
    static Potop strong;
    static List<Potop> liveList;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        // 포탑 입력 및 초기화
        p = new Potop[N][M];
        for(int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<M; j++) {
                int power = Integer.parseInt(st.nextToken());
                p[i][j] = new Potop(power, 0, i, j, false);
            }
        }


        // K번 진행
        for(int k=1; k<K+1; k++) {
            // 살아있는 포탑 정리
            liveList = new ArrayList<>();
            for(int i=0; i<N; i++) {
                for(int j=0; j<M; j++) {
                    if(p[i][j].power > 0) {
                        liveList.add(p[i][j]);
                    }
                }
            }
            // 살아있는 포탑이 1개 이하면 중단
            if(liveList.size() <= 1){
                break;
            }

            find();

            // System.out.println("w: "+weak);
            // System.out.println("s: "+strong);
            weak.power += (N+M);
            // System.out.println("weak power : "+weak.power);
            weak.isPre = true;
            weak.lastTime = k;
            if(!bfs(weak.x, weak.y)) {
                // System.out.print("던지기 실행");
                drop();
            }
            // System.out.println("공격후");
            // print();

            reward();
            // System.out.println("정비후");
            // print();
        }

        // 정답 출력
        int ans = Integer.MIN_VALUE;
        for(int i=0; i<N; i++) {
            for(int j=0; j<M; j++) {
                if(p[i][j].power > ans){
                    ans = p[i][j].power;
                }
            }
        }
        System.out.println(ans);


    }
    public static void print() {
        for(int i=0; i<N; i++) {
            for(int j=0; j<M; j++) {
                System.out.print("("+p[i][j].power +","+p[i][j].isPre+")");
            }
            System.out.println();
        }
    }
    // 공격자와 대상자 찾기
    public static void find() {
				// 살아있는 포탑 정렬
        Collections.sort(liveList);

        // 2. 공격자와 대상자 찾기
        weak = liveList.get(0);
        strong = liveList.get(liveList.size()-1);   // 대상자 조건은 공격자와 반대
    }
    static class Pos {
        int x, y;
        public Pos(int x, int y) {
            this.x = x;
            this.y = y;
        }
        public String toString() {
            return "("+this.x+","+this.y+")";
        }
    }
    public static boolean bfs(int sx, int sy) {
        boolean[][] visited = new boolean[N][M];
        Queue<Pos> q = new LinkedList<>();
        Pos[][] predecessor = new Pos[N][M];
        boolean isOk = false;

        // predecessor 초기화
        for(int i=0; i<N; i++) {
            for(int j=0; j<M; j++) {
                predecessor[i][j] = new Pos(0, 0);
            }
        }

        visited[sx][sy] = true;
        q.add(new Pos(sx, sy));
        while(!q.isEmpty()) {
            Pos now = q.poll();
            if(now.x == strong.x && now.y == strong.y){
                isOk = true;
                break;
            }
            for(int i=0; i<4; i++) {
                int nx = (now.x + rdx[i] + N) % N;
                int ny = (now.y + rdy[i] + M) % M;
                if(p[nx][ny].power != 0 && !visited[nx][ny]) {
                    visited[nx][ny] = true;
                    predecessor[nx][ny] = now;
                    q.add(new Pos(nx, ny));
                }
            }
        }
        if(!isOk) {
            return isOk;
        }
        // 경로 출력
        // for(int i=0; i<N; i++) {
        //     for(int j=0; j<M; j++) {
        //         System.out.print(predecessor[i][j]);
        //     }
        //     System.out.println();
        // }

        //경로의 포탑
        Pos pre = predecessor[strong.x][strong.y];
        while (true) {
            if (pre.x == weak.x && pre.y == weak.y) {
                break;
            }
            p[pre.x][pre.y].power -= (weak.power / 2);
            p[pre.x][pre.y].isPre = true;

            pre = predecessor[pre.x][pre.y];
        }        

        // 대상자의 포탑
        strong.power -= weak.power;
        strong.isPre = true;
        return isOk;
    }
    // 포탑 던지기
    public static void drop() {
        // 경로 포탑
        for(int i=0; i<8; i++) {
            int nx = (strong.x + tdx[i] + N) % N;
            int ny = (strong.y + tdy[i] + M) % M;
            if(nx == weak.x && ny == weak.y) {
                continue;
            }
            if(p[nx][ny].power != 0) {
                // System.out.println("("+nx+","+ny+")");
                p[nx][ny].power -= (weak.power / 2);
                p[nx][ny].isPre = true;
            }
        }
        // 대상자 포탑
        strong.power -= weak.power;
        strong.isPre = true;
    }

    // 포탑 부서짐 & 포탑 정비
    public static void reward() {
        for(int i=0; i<N; i++) {
            for(int j=0; j<M; j++) {
                if(!p[i][j].isPre) {
                    if(p[i][j].power != 0){
                        p[i][j].power += 1;
                    }
                } else{
                    // 이전에 공격 당했던 것들이 0보다 작으면 0으로 초기화
                    if(p[i][j].power < 0){
                        p[i][j].power = 0;
                    }
                    p[i][j].isPre = false;
                }
            }
        }
    }
}

 

주석이 너무 많다고요?

복잡하다고요?

읽기 어렵다고요?

그럴리가요?

도움이 정말 된다고요?

감사합니다~