오 나의 여신님

문제 :https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWsBQpPqMNMDFARG&categoryId=AWsBQpPqMNMDFARG&categoryType=CODE&&&

SW Expert Academy

알고리즘

1. time step 마다 악마를 증식시키고 주인공이 움직인다.

2. 악마 큐와 주인공 큐를 따로 만들어서 BFS를 사용하여 조건에 따라 증식 & 이동한다.

3. time step 마다 움직여야 하기 때문에 큐에 cnt를 만들어 time변수와 cnt를 비교하여

다르면 while문을 빠져나오게 했다.

주의사항

1. 악마를 먼저 증식시키고 플레이어가 움직여야 한다.

-> 플레이어가 먼저 움직이고 악마를 증식시키면 시간마다 또 체크를 해야 한다.

2. 처음에 도착하면 끝내는 부분을 주인공 큐에서 poll 하면서 확인했는데 테스트 케이스

6개만 맞았었다. 이유는 큐에 poll하면서 확인하면 시간이 달라질 수 있어서다. 그래서

큐에 offer 하기 전에 확인하거나 poll 하고 cnt와 time 비교가 끝난 후 확인해야 한다.

구현

package algorithm;
import java.util.Arrays;
import java.util.LinkedList;
///////////////////////////////////////////////////////////////////
import java.util.Scanner;
import java.util.StringTokenizer;


import java.io.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;

class Solution_오나의여신님
{
    static int N;
    static char map[][];
    static int end[];
    static boolean check[][];
    static int dir[][] = {{-1,0},{1,0},{0,-1},{0,1}};
    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++) 
        {
            StringTokenizer s = new StringTokenizer(in.readLine()," ");
            N = Integer.parseInt(s.nextToken());
            int M = Integer.parseInt(s.nextToken());
            map = new char[N][M];
            end = new int[2];
            check = new boolean[N][M];
            LinkedList<int []> queue = new LinkedList<int[]>();
            LinkedList<int []> Devil = new LinkedList<int[]>();
            for (int i = 0; i <N; i++) {
                String t = in.readLine();
                for (int j = 0; j < M; j++) {
                    map[i][j] = t.charAt(j);
                    if(map[i][j] == 'D')
                    {
                        end[0] = i;
                        end[1] = j;
                    }
                    else if(map[i][j] == 'S') {
                        queue.offer(new int[] {i,j,0});
                        check[i][j] = true;}
                    else if(map[i][j] == '*')
                        Devil.offer(new int[] {i,j,0});
                }
            }
            int time=1;
            boolean flag=false;
            TOP:
            while(!queue.isEmpty() && !flag)
            {
                while(!Devil.isEmpty()) 
                {
                    int temp[] = Devil.poll();
                    int y = temp[0];
                    int x = temp[1];
                    int cnt = temp[2];
                    if(cnt != time)
                    {
                        Devil.offerFirst(new int[] {y,x,cnt});
                        break;
                    }
                    for (int i = 0; i < 4; i++) {
                        int ny = y + dir[i][0];
                        int nx = x + dir[i][1];
                        if(ny >-1 &&nx>-1 &&ny<N &&nx<M && map[ny][nx]!='X' && map[ny][nx]!='D' && map[ny][nx] !='*')
                        {
                            Devil.offer(new int [] {ny,nx,cnt+1});
                            map[ny][nx] = '*';
                        }
                    }//map[i][j]가 D와 X가 아니면 악마가 퍼진다.
                }
                while(!queue.isEmpty())
                {
                    int temp[] = queue.poll();
                    int y = temp[0];
                    int x = temp[1];
                    int cnt = temp[2];
                    if(cnt != time)
                    {
                        queue.offerFirst(new int[] {y,x,cnt});
                        break;
                    }
                    for (int i = 0; i < 4; i++) {
                        int ny = y + dir[i][0];
                        int nx = x + dir[i][1];
                        if(ny >-1 &&nx>-1 &&ny<N &&nx<M && map[ny][nx]!='X' && map[ny][nx]!='*' && !check[ny][nx])
                        {
                            if(ny == end[0] && nx == end[1])
                            {
                                flag = true;
                                break TOP;
                            }
                            check[ny][nx] = true;
                            map[ny][nx] = 'S';
                            queue.offer(new int [] {ny,nx,cnt+1});
                        }
                    }
                }
                time++;
            }
            System.out.print("#"+test_case+" ");
            if(flag)
                System.out.println(time);
            else
                System.out.println("GAME OVER");
        }//endTK



    }


}

다른 방법