Baekjoon[17135] - 캐슬 디펜스

링크

17135번: 캐슬 디펜스

문제설명

• 완전탐색 + 시뮬레이션

문제풀이

• 완전탐색 + 시뮬레이션
• 완전탐색 << 시뮬레이션

문제코드

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main17135 {

    public static int Ans=Integer.MIN_VALUE;
    public static int Temp=0;
    public static int N;
    public static int M;
    public static int D;
    public static int[][] map;
    public static int[][] n_map;
    public static boolean [][] visit;
    public static LinkedList<int[]> target_lst = new LinkedList<int[]>();

    public static int[] comb = new int[3];

//    좌상우로만 퍼지면 됨.
    public static int dir[][] = {
            {0,-1},        //좌    
            {-1,0},        //상
            {0,1}        //우
    };

    public static void target(int c) {
        int sr = N-1;
        int sc = c;

        visit = new boolean[N+1][M];
//        궁수배치칸은 방문불가(어차피 방향이 밑으로탐색은 없음)
        for (int i = 0; i < M; i++) {
            visit[N][i]=true;
        }
        LinkedList<int[]> q = new LinkedList<int[]>();

        q.add(new int[] {sr,sc});
        visit[sr][sc]=true;
        int[] now;
        int range=1;
        int qsize;
        int nr;
        int nc;
        while(!q.isEmpty()) {
            if(range>D)return;
            qsize = q.size();
            for (int i = 0; i < qsize; i++) {
                now = q.poll();
//                사정범위 내에 적을 찾았으면 target_lst에 저장후 탐색종료
                if(n_map[now[0]][now[1]]==1) {
                    target_lst.add(now);
                    return;
                }

                for (int d = 0; d < 3; d++) {
                    nr = now[0] + dir[d][0];
                    nc = now[1] + dir[d][1];
//                    경계 안이고, 방문 가능할 때,
                    if (nr>=0 && nr<N && nc>=0 && nc<M && !visit[nr][nc]) {
                        q.add(new int[] {nr,nc});
                        visit[nr][nc]=true;
                    }
                }
            }
//            다음 사정거리 내 적 검사
            range++;
        }
    }

    public static void shoot() {
//        target_lst 기준으로 그 좌표의 적들 제거
        int size = target_lst.size();
        int[] now;
        for (int i = 0; i < size; i++) {
            now = target_lst.get(i);
//            적이있으면 죽이고
            if (n_map[now[0]][now[1]]==1) {
                n_map[now[0]][now[1]] = 0;
                Temp++;
            }
//            없으면 이미죽임 (중복)
        }
    }

    public static void down() {
        for (int i = N-1; i > 0; i--) {
            n_map[i] = Arrays.copyOf(n_map[i-1], M);
        }
        n_map[0] = new int[M];
    }

    public static void Search(int cnt, int start, int flag) {
        if(cnt==3) {
//            comb 기준으로
//            System.out.println(Arrays.toString(comb));
//            궁수 3명이 배치시키는 조합 완성
//            n_map 재설정
            for (int i = 0; i < N+1; i++) {
                for (int j = 0; j < M; j++) {
                    n_map[i][j] = map[i][j];
                }
            }
//            궁수 3명 배치
            for (int i = 0; i < 3; i++) {
                n_map[N][comb[i]]=1;
            }
//            최대 N번 내려감
            Temp=0;
            for (int time = 1; time <= N; time++) {
                for (int i = 0; i < M; i++) {
//                    궁수가 배치되어있으면
                    if(n_map[N][i]==1) {
//                        타겟 찾아서 좌표저장
                        target(i);
                    }
                }
//                좌표에 저장된 타겟들 제거
                shoot();
//                적 한칸씩 이동
                down();
//                초기화
                target_lst.clear();
            }
            Ans = Math.max(Ans, Temp);
            return;
        }


        for (int i = start; i < M; i++) {
            if((flag & 1<<i)==0) {
                comb[cnt]=i;
                Search(cnt+1,i,flag|1<<i);
            }
        }
    }

    public static void main(String[] args) throws NumberFormatException, IOException {
        System.setIn(new FileInputStream("res/baekjoon/17135.txt"));
        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+1][M];
        n_map = new int[N+1][M];

        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());
                n_map[i][j] = map[i][j];
            }
        }

        Search(0,0,0);

        System.out.println(Ans);
//        초기화
        Ans=Integer.MIN_VALUE;
    }
}

아쉬운점

• dir 상이 {-1,0} 인데 {1,0}으로 함...
• down 메서드 만들 때, index 범위 초과했었음
  • N은 궁수배치하는공간인데 N까지 down시키려했었음
• 메서드 다만들어놓고 조합을 안만들었었음

잘한점

• 문제 꼼꼼히 읽었음
  • 동시공격할 경우
    • 제일 왼쪽을 고려한다
      • BFS를 {좌, 상, 우} 순서대로 탐색을 시키면 자동으로 왼쪽먼저 고려하게 된다.
      • 아니면 매번 같은 range의 target을 list에 정렬 후 c기준으로 정렬 후 첫 원소를 선택했어야 했음.
    • 동시에 공격할 경우
      • list만들어서 좌표 저장한 후에 제거하고, 이미 제거된거면 count안하면 된다.
• O(N) = 15C3 * 3*BFS(depth-D)*N(down) = 안터짐
• 초기화 안까먹음
• 빨리품(1시간10분)
  • 예전엔 구현 귀찮아서 하다 말았는데 이젠 할만한듯