[코딩테스트] SWEA 7793 오! 나의 여신님(Java)

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
SWEA 7793 오! 나의 여신님입니다.

포인트

해당 문제에서는 악마의 손아귀가 먼저 진행되어야 합니다.

만약 악마의 손아귀를 통해서 전파된 곳에 수연이가 이미 있는 곳이라도 사실 크게 의미가 없습니다.

왜냐하면 이미 수연이가 있는 위치는 수연이가 도달한 공간이기 때문에 다음 시간에는 수연이가 이동하기에 부식된 공간과는 수연이의 위치와 무관합니다. 수연이가 고려할 것은 다음 위치에 악마의 손아귀가 있는지 없는지 입니다.

따라서 BFS 탐색을 통해서 문제를 진행합니다.

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Q7793 {
    static class Pair {
        int x, y;

        public Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    private static int tc, N, M, ans;
    private static char[][] map;
    private static int[][] step;
    private static boolean[][] visited;
    private static int[] dx = {-1, 0, 1, 0};
    private static int[] dy = {0, 1, 0, -1};
    private static Pair angle, su;
    private static List<Pair> demons;

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

        for (int t = 1; t <= tc; t++) {
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
            map = new char[N][M];
            step = new int[N][M];
            visited = new boolean[N][M];
            demons = new ArrayList<>();
            ans = Integer.MAX_VALUE;

            for (int i = 0; i < N; i++) {
                String line = br.readLine();
                for (int j = 0; j < M; j++) {
                    map[i][j] = line.charAt(j);
                    if (map[i][j] == 'D') {
                        angle = new Pair(i, j);
                    } else if (map[i][j] == 'S') {
                        su = new Pair(i, j);
                    } else if (map[i][j] == '*') {
                        demons.add(new Pair(i, j));
                    }
                }
            }

            int answer = bfs();

            sb.append("#").append(t).append(" ")
                    .append(answer == -1 ? "GAME OVER" : answer)
                    .append("\n");
        }
        System.out.println(sb);
    }

    static int bfs() {
        Queue<Pair> suyeonQ = new LinkedList<>();
        Queue<Pair> demonQ = new LinkedList<>();
        suyeonQ.add(su);
        demonQ.addAll(demons);

        while (!suyeonQ.isEmpty()) {
            // 1. 악마 먼저 퍼짐
            int demonSize = demonQ.size();
            for (int i = 0; i < demonSize; i++) {
                Pair d = demonQ.poll();
                for (int dir = 0; dir < 4; dir++) {
                    int nx = d.x + dx[dir];
                    int ny = d.y + dy[dir];
                    if (canGo(nx, ny) && map[nx][ny] != 'D') {
                        map[nx][ny] = '*';
                        demonQ.offer(new Pair(nx, ny));
                    }
                }
            }

            // 2. 수연이 이동
            int suSize = suyeonQ.size();
            for (int i = 0; i < suSize; i++) {
                Pair s = suyeonQ.poll();
                for (int dir = 0; dir < 4; dir++) {
                    int nx = s.x + dx[dir];
                    int ny = s.y + dy[dir];
                    if (canGo(nx, ny)) {
                        if (map[nx][ny] == '*') {
                            continue;
                        } else if (map[nx][ny] == 'D') {
                            return step[s.x][s.y] + 1;
                        }
                        visited[nx][ny] = true;
                        step[nx][ny] = step[s.x][s.y] + 1;
                        suyeonQ.offer(new Pair(nx, ny));
                    }
                }
            }
        }
        return -1;
    }

    private static boolean canGo(int x, int y) {
        if (!inRange(x, y)) return false;
        if (visited[x][y] || map[x][y] == 'X' || map[x][y] == '*') return false;

        return true;
    }

    private static boolean inRange(int x, int y) {
        return 0 <= x && x < N && 0 <= y && y < M;
    }
}

/*
2
5 3
D*S
.X.
.X.
.X.
...
5 3
D*S
...
.X.
.X.
...
 */

코드 설명

• inRange(int x, int y)
  x, y가 격자 내에 존재하는지 판단하는 함수
• canGo(int x, int y)
  x, y가 갈 수 있는 위치인지 판단하는 함수
  • 격자 내에 존재하거나
  • 방문하지 않았던 점이거나
  • 돌이나 악마의 손아귀가 아닌 점일 시에 true를 반환합니다.
• bfs()
  bfs 탐색을 하는 함수
  • suyeonQ, demonQ를 선언합니다.
    • suyeonQ: 수연이의 위치를 저장하는 Queue
    • demonQ: 악마의 손아귀의 위치를 저장하는 Queue
  • suyeonQ.isEmpty()가 아닐동안
    • 악마의 손아귀를 먼저 진행
      • 현재 시점의 큐 크기(demonSize)만큼만 반복하여, 같은 시간대의 악마의 손아귀만 처리하고 다음 단계는 다음 턴에 처리
      • 갈 수 있을 때(canGo(nx, ny) && map[nx][ny] != 여신)
        • demonQ에 저장
    • 수연이 이동
      • 현재 시점의 큐 크기(suSize)만큼만 반복하여, 같은 시간대의 수연이 이동만 처리하고 다음 단계는 다음 턴에 처리 
      • step[][] 배열을 통해 이전 위치 + 1을 저장
      • 만약 다음 canGo에 여신이면 step[s.x][s.y] + 1 반환.