SWEA 7793 오! 나의 여신님 (BFS)

SW Expert Academy

아래 두문제와 매우 유사한 문제다

5427번: 불

3055번: 탈출

이 문제는 Queue를 2개를 써서 악마, 사람의 움직임을 관리해주면 된다.

Point는 1개의 BFS안에서 2개의 Queue를 쓰는 것이다.

 

악마와 사람이 동시에 움직여야하는데 사람 ->  악마로 순서를 잡으면 고려해야 될 께 너무 많아지는데

악마 -> 사람 순서로 하면 간단하게 끝난다.

 

악마가 상하좌우로 퍼져나가는 곳에 *로 박아버리면 사람이 상하좌우 탐색을 하면서 *를 만났을 땐 다음턴에 지금 있는 위치가 악마가 오는 자리라는걸 알 수 있다.

 

사실 대단한 스킬을 요구하는건 아니다.

nx,ny는 이제 곧 방문할 곳을 queue에 넣는것이고 그 자리를 *로 바꿔주는 행위니까!

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class Solution_7793 {
    static int N,M;
    static char[][] board;
    static int[] dx = {1,-1,0,0};
    static int[] dy = {0,0,1,-1};

    static Queue<int[]> devilQueue;
    static Queue<int[]> personQueue;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int T = Integer.parseInt(st.nextToken());

        for (int tc = 1; tc < T+1; tc++) {
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());

            devilQueue = new ArrayDeque<>();
            personQueue = new ArrayDeque<>();
            board = new char[N][M];

            for (int i = 0; i < N; i++) {
                String input = br.readLine();
                for (int j = 0; j < M; j++) {
                    board[i][j] = input.charAt(j);
                    if (board[i][j] == 'S'){
                        personQueue.add(new int[]{i,j,0});
                    }
                    else if (board[i][j] == '*'){
                        devilQueue.add(new int[]{i,j});
                    }
                }
            }

            int res = bfs();

            if (res == -1)
                System.out.println("#"+tc+" GAME OVER");
            else
                System.out.println("#"+tc+" "+res);

        }
    }

    public static int bfs(){
        while (!personQueue.isEmpty()){
            //악마 이동
            int length = devilQueue.size();
            for (int i = 0; i < length; i++) {
                int[] poll_data = devilQueue.poll();
                int x = poll_data[0];
                int y = poll_data[1];
                for (int j = 0; j < 4; j++) {
                    int nx = x + dx[j];
                    int ny = y + dy[j];
                    if (nx<0 || ny<0 || nx>=N || ny>=M)
                        continue;
                    if (board[nx][ny] == '.' || board[nx][ny] == 'S'){
                        board[nx][ny] = '*';
                        devilQueue.add(new int[]{nx,ny});
                    }
                }
            }

            //사람 이동
            length = personQueue.size();
            for (int i = 0; i < length; i++) {
                int[] poll_data = personQueue.poll();
                int x = poll_data[0];
                int y = poll_data[1];
                int cnt = poll_data[2];

                for (int j = 0; j < 4; j++) {
                    int nx = x + dx[j];
                    int ny = y + dy[j];

                    if (nx<0 || ny<0 || nx>=N || ny>=M)
                        continue;

                    if (board[nx][ny] == 'D')
                        return cnt+1;


                    if (board[nx][ny] == '.'){
                        board[nx][ny] = 'S';
                        personQueue.add(new int[]{nx,ny,cnt+1});
                    }
                }
            }
        }
       return -1;
    }

}