SWEA[5650] - 핀볼 게임

링크

SWEA[5650]

문제설명

• 시뮬레이션

문제풀이

• 시뮬레이션

문제코드

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.StringTokenizer;

public class Solution5650 {

    public static int[][] dir = {
            {-1,0},    
            {1,0},    
            {0,-1},    
            {0,1}    
    };
    public static int Ans = 0;
    public static int Temp = 0;
    public static int[][] map;
    public static ArrayList<int[]>[] hole;
    public static int N;
    public static int sr;
    public static int sc;

    public static void Simulation(int[] rc , int now_dir) {
        int nr;
        int nc;
        while(true) {
//            다음칸 이동
            nr = rc[0] + dir[now_dir][0];
            nc = rc[1] + dir[now_dir][1];

            int next_dir = -1;

//            경계 안에서
            if(nr>=0 && nr<N && nc>=0 && nc<N) {
//            다음칸이 블랙홀이면
                if(map[nr][nc]==-1) {
                    Ans = Math.max(Ans, Temp);
                    break;
                }
//            다음칸이 처음 위치면
                if(nr == sr && nc == sc) {
                    Ans = Math.max(Ans, Temp);
                    break;
                }
//            다음칸으로 이동할 경우
                switch (map[nr][nc]) {
//                그대로
                case 0:
                    next_dir = now_dir;
                    break;
                case 1:
                    Temp++;
                    switch (now_dir) {
//                    상->하
                    case 0:
                        next_dir = 1;
                        break;
//                    하->우
                    case 1:
                        next_dir = 3;
                        break;
//                    좌->상
                    case 2:
                        next_dir = 0;
                        break;
//                    우->좌
                    case 3:
                        next_dir = 2;
                        break;
                    }
                    break;
                case 2:
                    Temp++;
                    switch (now_dir) {
//                    상->우
                    case 0:
                        next_dir = 3;
                        break;
//                    하->상
                    case 1:
                        next_dir = 0;
                        break;
//                    좌->하
                    case 2:
                        next_dir = 1;
                        break;
//                    우->좌
                    case 3:
                        next_dir = 2;
                        break;
                    }
                    break;
                case 3:
                    Temp++;
                    switch (now_dir) {
//                    상->좌
                    case 0:
                        next_dir = 2;
                        break;
//                    하->상
                    case 1:
                        next_dir = 0;
                        break;
//                    좌->우
                    case 2:
                        next_dir = 3;
                        break;
//                    우->하
                    case 3:
                        next_dir = 1;
                        break;
                    }
                    break;
                case 4:
                    Temp++;
                    switch (now_dir) {
//                    상->하
                    case 0:
                        next_dir = 1;
                        break;
//                    하->좌
                    case 1:
                        next_dir = 2;
                        break;
//                    좌->우
                    case 2:
                        next_dir = 3;
                        break;
//                    우->상
                    case 3:
                        next_dir = 0;
                        break;
                    }
                    break;
                case 5:
                    Temp++;
                    switch (now_dir) {
//                    상->하
                    case 0:
                        next_dir = 1;
                        break;
//                    하->상
                    case 1:
                        next_dir = 0;
                        break;
//                    좌->우
                    case 2:
                        next_dir = 3;
                        break;
//                    우->좌
                    case 3:
                        next_dir = 2;
                        break;
                    }
                    break;
                case 6:
                case 7:
                case 8:
                case 9:
                case 10:
                    next_dir = now_dir;
//                첫번째 홀인경우
                    int[] nrc;
                    if (hole[map[nr][nc]].get(0)[0]== nr && hole[map[nr][nc]].get(0)[1]== nc) {
                        nrc = hole[map[nr][nc]].get(1);
                        nr = nrc[0];
                        nc = nrc[1];
                    }
//                두번째 홀인경우
                    else {
                        nrc = hole[map[nr][nc]].get(0);
                        nr = nrc[0];
                        nc = nrc[1];
                    }
                    break;
//            블랙홀 -> 일단 넘어감
                case -1:
                    next_dir = now_dir;
                    break;
                }
//                다음 단계로 넘어감
                rc = new int[] {nr,nc};
                now_dir = next_dir;
            }
//        벽을 만난 경우
            else {
                Temp++;
                switch (now_dir) {
                case 0:
                    next_dir=1;
                    break;
                case 1:
                    next_dir=0;
                    break;
                case 2:
                    next_dir=3;
                    break;
                case 3:
                    next_dir=2;
                    break;
                }
//                다음 단계로 넘어감
                rc = new int[] {nr,nc};
                now_dir = next_dir;
            }

        }
    }

    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("res/swea/5650.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int T=Integer.parseInt(br.readLine());
        for (int test_case = 1; test_case <= T; test_case++) {
//            입력
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            map = new int[N][N];
            hole = new ArrayList[11];    //[6~10]
            for(int i=0; i<11; i++) {
                   hole[i] = new ArrayList<int[]>(); // 배열에 Class를 지정하여 ArrayList 저장
            }

//            map 입력
            for (int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < N; j++) {
                    map[i][j] = Integer.parseInt(st.nextToken());
                }
            }
//            웜홀 정보 입력
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if(map[i][j]>0) {
                        hole[map[i][j]].add(new int[] {i,j});
                    }
                }
            }

            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if(map[i][j]==0) {
                        for (int d = 0; d < 4; d++) {
                            Temp=0;
                            sr=i;
                            sc=j;
                            Simulation(new int[] {i,j},d);
                        }
                    }
                }
            }

//            Temp=0;
//            sr=2;
//            sc=3;
//            Simulation(new int[] {2,3},3);

            System.out.println("#"+test_case+" "+Ans);
            /*
             * 초기화
             */
            Ans=0;
        }//end test_case
    }//end main
}

아쉬운점

• 웜홀 입력받는게 까다로웠음
• array list 배열 생성하는 법 몰랐음
  • hole = new ArrayList[11]; 선언 후  
  • 각 array 공간마다 arraylist배정해줘야함.
• 끝나는 조건 설정 잘못함
  • 처음부터 sr,sc하면 막힘
  • 다음칸부터 sr,sc비교
• 웜홀 좌표 업데이트 하는 도중에 참조값이 변해서 다음참조를 잘못함.
  • nr = hole[map[nr][nc]].get(1)[0];
  • nc = hole[map[nr][nc]].get(1)[1];
  • nr 업데이트하면서 map[nr]바뀜
• 재귀함수로 짜니 스택 오버플로우 떴음
  • Depth 고려 못했음
  • Max Depth = 100*100*2 모든경로 왕복할 경우 -> 터짐

잘한점

• 완전탐색 O(N) = 100*100*4(방향)*Simulation = 40000*Simulation 안터짐
• 재귀함수 Depth 터지는거 직접 깨닫고... While문으로 바꿈
• Switch문 잘 사용했음
  • 6~10을 한번에 처리했음
• 완전탐색할 때 전역변수 미리 초기화시킴(까먹지말자)