코드트리 - 팩맨

---

1. 문제 분석

1. 알낳기

2. 몬스터 잡기

3. 시체 

 

크게 3개의 메소드로 구현하였다.

 

 

 

2. 전체 소스

package test;
 
import java.util.*;
import java.io.*;
 
public class Main {
    public static int monster, repeat;
    public static final int size = 4;
    public static final int p_num = 4;
    public static final int m_num = 8;
    public static final int max_repeat = 25;
    public static final int dead_repeat = 2;
    public static int[][][][] mon_arr = new int[max_repeat+1][size][size][m_num];
    public static int[][][] dead = new int[size][size][dead_repeat+1];
 
    public static Queue<int[]> q = new LinkedList<>();
 
    public static int eat_check = 0;
    
 
    public static int[] mdx = {-1,-1,0,1,1,1,0,-1};
    public static int[] mdy = {0,-1,-1,-1,0,1,1,1};
    public static int[] pdx = {-1,0,1,0};
    public static int[] pdy = {0,-1,0,1};
 
    public static int px, py;
    public static int now_repeat=1;
 
    public static boolean p_same(int x, int y){
        return x==px && y==py;
    }
 
    //격자 넘어가는지 체크
    public static boolean over(int x, int y){
        return x>=0 && y>=0 && x<size && y<size;
    }
 
    public static boolean canGo(int x, int y){
    	if(over(x,y)) {
    //	System.out.println("x: "+x +"y: "+y +"  dead[0]: "+dead[x][y][0] + "  dead[1]: "+dead[x][y][1]);
    	}
        return over(x,y) && !p_same(x,y) && dead[x][y][0]==0 && dead[x][y][1]==0;
    }
 
    public static void print(){
        System.out.println("-----------위치----------------");
        
        
            for(int i=0; i<size; i++){
                for(int j=0; j<size; j++){
                    int sum = 0;
                    for(int w=0; w<m_num; w++){
                        sum += mon_arr[now_repeat][i][j][w];
                    }
                    if (sum!=0) System.out.println(i+" "+j+" "+sum);
                }
            }
        System.out.println("-------------------------");
    }
 
    //0. 알 낳았던게 부활
    public static void egg(){
        for(int i=0; i<size; i++){
            for(int j=0; j<size; j++){
                for(int w=0; w<m_num; w++){
                    mon_arr[now_repeat][i][j][w] += mon_arr[now_repeat-1][i][j][w];
                }
            }
        }
 
    }
 
    public static void m_move(){
        for(int i=0; i<size; i++){
            for(int j=0; j<size; j++){
                for(int w=0; w<m_num; w++){
                    if(mon_arr[now_repeat-1][i][j][w]>0){
                        boolean check = false;
                        for(int t=0; t<m_num; t++){
                            int p = (w + t + m_num) % m_num ;
                            int mx = i + mdx[p];
                            int my = j + mdy[p];
                            if(canGo(mx,my)){
                                mon_arr[now_repeat][mx][my][p] += mon_arr[now_repeat-1][i][j][w];
                                check = true;
                                break;
                            }
                        }
                        if(!check){
                            mon_arr[now_repeat][i][j][w] += mon_arr[now_repeat-1][i][j][w]; 
                        }
                    }
                }
            }
        }
    }
 
    public static int get_Eat(){
        //번째, 잡은 몬스터, x, y 
        q.offer(new int[] {0,0,px,py}); 
        int max = 0;
 
        while(true){
            int[] p = q.poll();
            int r = p[0];
            int x = p[2];
            int y = p[3];
            int x_2 = 0 ;
            int y_2 = 0 ;
 
            if(r==2){
                x_2 = p[4];
                y_2 = p[5];
            }else if(r==3){
                q.offer(new int[] {p[0],p[1],p[2],p[3],p[4],p[5],p[6],p[7]});
                break;
            }
            for(int i=0; i<p_num; i++){
                int mx = x + pdx[i];
                int my = y + pdy[i];
                int eat = p[1];
                int cnt = 0;
                if(over(mx,my)){
                    for(int w=0; w<m_num; w++){
                        cnt += mon_arr[now_repeat][mx][my][w];
                    }
                eat += cnt;
                if(r==2){
                    if(mx==x_2 && my==y_2){
                                eat -= cnt;
                            }
                        }
 
                    if(r==0){
                        // System.out.println("1번: "+eat+"먹고 "+mx+" "+my);
                        q.offer(new int[] {r+1,eat,mx,my});
                    }else if(r==1){
                        // System.out.println("2번: "+eat+"먹고 "+mx+" "+my);
                        q.offer(new int[] {r+1,eat,mx,my,x,y});
                    }else if(r==2){
                        // System.out.println("3번: "+eat+"먹고 "+mx+" "+my);
                        q.offer(new int[] {r+1,eat,mx,my,x,y,x_2,y_2});
                    }
                }
            }
        }
 
        while(q.size()!=1){
            
            int[] p = q.poll();
            int eat = p[1];
            // System.out.println(p[2]+" "+p[3]+" eat: "+eat);
            if(eat>max){
                max = eat;
                q.offer(new int[] {p[0],p[1],p[2],p[3],p[4],p[5],p[6],p[7]});
            }
        }
 
        return max;
 
    }
 
    // 시체남기기
    public static void dead_mon(){
        int[] p = q.poll();
        
        //if(eat_check != 0){
            
            for(int w=0; w<m_num; w++){
                if(mon_arr[now_repeat][p[2]][p[3]][w]>0){
                    dead[p[2]][p[3]][dead_repeat] = 2;
             //       System.out.println(p[2]+" "+p[3]);
                }
 
                if(mon_arr[now_repeat][p[4]][p[5]][w]>0){
                    dead[p[4]][p[5]][dead_repeat] = 2;
            //        System.out.println(p[4]+" "+p[5]);
                }
 
                if(mon_arr[now_repeat][p[6]][p[7]][w]>0){
                    dead[p[6]][p[7]][dead_repeat] = 2;
             //       System.out.println(p[6]+" "+p[7]);
                }
 
                mon_arr[now_repeat][p[2]][p[3]][w] = 0;
                mon_arr[now_repeat][p[4]][p[5]][w] = 0;
                mon_arr[now_repeat][p[6]][p[7]][w] = 0;
            }
 
 
      //  }
 
        px = p[2];
        py = p[3];
 
        for(int i=0; i<size; i++){
            for(int j=0; j<size; j++){
                for(int r=0; r<dead_repeat; r++){
                    dead[i][j][r] = dead[i][j][r+1];
//                    System.out.println(dead[1][2][2]);
//                    System.out.println("x: "+i+"  y: "+j+"  r:"+r);
//                    System.out.println("dead[i][j][r]: "+dead[i][j][r] +"   dead[i][j][r+1]: "+dead[i][j][r+1]);
                }
                dead[i][j][dead_repeat] = 0 ;
            }
        }
        
    }
    
 
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        monster = Integer.parseInt(st.nextToken());
        repeat = Integer.parseInt(st.nextToken());
 
        //0. 팩맨은3, 몬스터는2, 알은1 로 가정하자.
        //1. 몬스터 복제시도(알 낳기)
        //2. 몬스터 이동 (팩맨,벽,시체 일경우 반시계반향 45도)
        //3. 팩맨이동(3칸 상,좌,하,우 우선순위)
        //4. 몬스터 시체 소멸(2턴유지, 다른배열 선언)
        //5. 몬스터 복제완성(알에서 부화 처음 알낳을때의 방향대로)
 
        st = new StringTokenizer(br.readLine());
        px = Integer.parseInt(st.nextToken())-1;
        py = Integer.parseInt(st.nextToken())-1;
 
        for(int i=0; i<monster; i++){
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken())-1;
            int y = Integer.parseInt(st.nextToken())-1;
            int way = Integer.parseInt(st.nextToken())-1;
            mon_arr[0][x][y][way]=1;
        }
 
        for(int t=0; t<repeat; t++){
            m_move();
            print();
            get_Eat();
            dead_mon();
            egg();
            now_repeat++;
        }
 
 
    int result = 0;
        for(int i=0; i<size; i++){
            for(int j=0; j<size; j++){
                for(int w=0; w<m_num; w++){
                    result += mon_arr[now_repeat-1][i][j][w];
                }
            }
        }
        
        System.out.println(result);
 
    }
}JAVA

 

현재 여기까지 구현하였는데 16% 부터 막혔다..