SWEA 7793 오! 나의 여신님(JAVA) 👸

구조화

• bfs start(수연이의 좌표) → end(여신님 좌표)
• 악마의 손아귀는 한 턴마다 *를 찾아 퍼지게 만들기
• 장애물은 ‘X’

순서

1. ‘S’ 수연 좌표 이동
   • 장애물 접근 X
   • ‘*’ 악마의 손아귀 범위내에 들어가면 GAME OVER
   • ‘D’ 여신님의 좌표에 도착하면 bfs 끝
2. 악마의 손아귀
   • ‘*’ 찾아서 인접 행열에 퍼트리기

소스 코드

package day1006;

import java.io.*;
import java.util.*;

public class Solution_7793_오나의여신님 {

    static int T, N, M;
    static char[][] map;
    static boolean[][] visited;
    static int suX, suY;
    static int godX, godY;
    static int result;
    static String resultStr = "GAME OVER";
    static boolean flag;
    // 동 서 남 북
    static int[][] way = {{0,1},{0,-1},{1,0},{-1,0}};
    public static void main(String[] args) throws NumberFormatException, IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        T = Integer.parseInt(br.readLine());

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

            // 초기화
            flag = false;
            result = 0;
            map = new char[N][M];
            visited = new boolean[N][M];
            // ---

            for (int i = 0; i < N; i++) 
            {
                String str = br.readLine();
                for (int j = 0; j < M; j++) 
                {
                    map[i][j] = str.charAt(j);

                    if(map[i][j] == 'S')
                    {
                        suX = i;
                        suY = j;
                    }
                    if(map[i][j] == 'D')
                    {
                        godX = i;
                        godY = j;
                    }
                }
            }

            bfs(suX, suY);
            if(flag) System.out.println("#"+t+" "+result);
            else System.out.println("#"+t+" GAME OVER");

        }
    }

    static void bfs(int x, int y) 
    {
        Queue<int[]> queue = new LinkedList<int[]>();
        queue.add(new int[] { x, y });

        find: while (!queue.isEmpty()) 
        {
            result++;

            int size = queue.size();
            devil();

            for (int s = 0; s < size; s++) 
            {
                int[] cur = queue.poll();
                x = cur[0];
                y = cur[1];
                visited[x][y] = true;

                for (int i = 0; i < 4; i++) 
                {
                    int cx = x + way[i][0];
                    int cy = y + way[i][1];

                    if (isRight(cx, cy)) 
                    {
                        // end 지점 여신님 만나는 시점
                        if(map[cx][cy] == 'D')
                        {
                            flag = true;
                            break find;
                        }
                        // 방문하지 않았고, 장애물이 아니라면
                        if (!visited[cx][cy] && map[cx][cy] == '.') 
                        {
                            queue.add(new int[] { cx, cy });
                            visited[cx][cy] = true;
                        }
                    }
                }
            }
        }
    }

    // 악마 퍼트리기
    private static void devil() {

        Queue<int[]> devilQ = findDevil();

        while (!devilQ.isEmpty()) 
        {
            int[] cur = devilQ.poll();
            int cx = cur[0];
            int cy = cur[1];

            for (int w = 0; w < 4; w++) 
            {
                int nx = cx+way[w][0];
                int ny = cy+way[w][1];

                // 경계 체크 & 장애물 체크
                if(isRight(nx, ny))
                {
                    if(map[nx][ny] == '.')
                    {
                        map[nx][ny] = '*';
                    }
                }
            }
        }
    }

    // 악마 좌표 찾기
    private static Queue<int[]> findDevil() {

        Queue<int[]> devilQ = new LinkedList<>();

        for (int i = 0; i < N; i++) 
        {
            for (int j = 0; j < M; j++) 
            {
                if(map[i][j] == '*')
                {
                    devilQ.add(new int[] {i,j});
                }
            }
        }
        return devilQ;
    }

    // 경계 체크 함수
    private static boolean isRight(int nx, int ny) {

        if(nx>=0 && nx<N && ny>=0 && ny<M)
            return true;

        return false;
    }

}