5650. [모의 SW 역량테스트] 핀볼 게임 (JAVA)

문제 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRF8s6ezEDFAUo

SW Expert Academy

 

문제설명

 

자료구조를 잘 활용하여 풀어야하는 시뮬레이션인다.

 

N의 크기가 100이기 때문에 값이 0인 자리에서 출발하여 모든 경우의 수를 살펴봐도 O(N^2)이다.

 

아마 평균적으로는 장애물들이 있기 때문에 훨씬 더 빠를 것이다.

 

알고리즘

 

1. 0이 있는곳 즉 아무 장애물이 없는 구역을 queue에 넣는다.

 

2. 하나씩 poll 하며 4방향으로 조건에 맞게 탐색을 진행한다.

 

3. 웜홀 같은 경우에는 리스트에 저장하여 탐색 시 번호는 같지만 좌표가 다른 것을 찾아 이동하였다.

 

주의사항

 

1. Tk 1개가 계속 틀려서 고민했다. 알고보니 웜홀의 조건이 잘못된 것이였다.

 

좌표가 다른 것을 찾을때 괄호를 안쳐 이상한 조건에 들어갔다.

 

2. 범위를 벗어나면 지금껏 갔던 길의 반대방향으로 가기 때문에 점수 *2 +1 하면 된다.

 

구현

 

class Solution
{
    static int N;
    static int map[][];
    static int dir[][] = {{-1,0},{1,0},{0,-1},{0,1}};
    static int max;
    static ArrayList<int []> hole = new ArrayList<int[]>();
    static LinkedList<int []> start = new LinkedList<int[]>();
    public static void main(String args[]) throws Exception
    {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(in.readLine().trim());
        for (int test_case = 1; test_case <= T; test_case++) 
        {
            hole.clear();
            start.clear();
            StringTokenizer s;
            N = Integer.parseInt(in.readLine().trim());
            map = new int[N][N];
            max = 0;
            for (int i = 0; i < N; i++) {
                s = new StringTokenizer(in.readLine()," ");
                for (int j = 0; j < N; j++) {
                    map[i][j] = Integer.parseInt(s.nextToken());
                    if(map[i][j]>5) //웜홀이면
                    {
                        hole.add(new int[] {i,j,map[i][j]});
                    }
                    else if(map[i][j] == 0)
                        start.add(new int[] {i,j});
                }
            }

            while(!start.isEmpty())
            {
                int [] temp = start.poll();
                int y = temp[0];
                int x = temp[1];
                //1. 4방향으로 탐색해야함
                for (int i = 0; i < 4; i++) 
                {
                    int score = 0;
                    int ny = y;
                    int nx = x;
                    int direc = i;
                    while(true)//종료조건 자신자리로 돌아오거나 ,블랙홀
                    {
                        ny+=dir[direc][0];
                        nx+=dir[direc][1];
                        if(ny > -1 && nx>-1 && nx < N&&ny<N)
                        {
                            if(map[ny][nx] == -1 || (ny == y&& nx == x))
                            {
                                break;
                            }
                            else if(map[ny][nx] > 5) //웜홀이면
                            {
                                for (int j = 0; j < hole.size(); j++) {
                                    if(hole.get(j)[2] == map[ny][nx] && (hole.get(j)[0] != ny || hole.get(j)[1] != nx))
                                    {
                                        ny = hole.get(j)[0];
                                        nx = hole.get(j)[1];
                                        break;
                                    }
                                }
                            }
                            else if (map[ny][nx] != 0) //1~5가됌
                            {
                                switch (map[ny][nx]) {
                                case 1:  //하 좌 1 2 
                                    if(direc == 1) //하는 우로감
                                        direc = 3;
                                    else if(direc == 2)//좌는 상으로감
                                        direc = 0;
                                    else if (direc == 0)
                                        direc = 1;
                                    else if(direc == 3)
                                        direc = 2;
                                    break;
                                case 2: //상으로 가면 우  좌로가면 하
                                    if(direc == 1) //하는 우로감
                                        direc = 0;
                                    else if(direc == 2)//좌는 상으로감
                                        direc = 1;
                                    else if (direc == 0)
                                        direc = 3;
                                    else if(direc == 3)
                                        direc = 2;
                                    break;
                                case 3: //상으로 가면 좌 우로가면 하
                                    if(direc == 0)
                                        direc = 2;
                                    else if(direc == 1)
                                        direc = 0;
                                    else if (direc == 2)
                                        direc = 3;
                                    else if(direc == 3)
                                        direc = 1;
                                    break;
                                case 4: //하로가면 좌 우로가면 상
                                    if(direc == 0) 
                                        direc = 1;
                                    else if(direc == 1)
                                        direc = 2;
                                    else if (direc == 2)
                                        direc = 3;
                                    else if(direc == 3)
                                        direc = 0;
                                    break;
                                case 5: //하로가면 좌 우로가면 상
                                    if(direc == 0)
                                        direc = 1;
                                    else if(direc == 1)
                                        direc = 0;
                                    else if(direc == 2)
                                        direc = 3;
                                    else if(direc == 3)
                                        direc = 2;
                                    break;
                                }
                                score++;
                            }
                        }
                        else //범위 벗어나면
                        {
                            score=score*2+1;
                            break;
                        }
                    }//end while
                    if(score > max)
                        max = score;
                }//end for
            }//end while
            System.out.println("#"+test_case+" "+max);
        }

    }

}