[자바] SWEA 7793 : 오! 나의 여신님 (D5)

[자바] SWEA 7793 : 오! 나의 여신님 (D5)

• SWEA 7793 : 오! 나의 여신님

---

풀이

방향성 생각

• 멀티소스 BFS
• 악마의 우선순위가 캐릭터의 우선순위보다 높게 설정해서 문제 풀이한다.
  • 큐에 먼저 담아주면 된다.
  • 악마는 여러개인 것에 주의하기

 

전체코드

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

public class Solution {
    static int H, W;
    static char[][] arr;
    static int[][] V;
    static int[][] dires = {{1,0},{0,1},{-1,0},{0,-1}};

    // validation
    static boolean inside(int x, int y) {
        return 0 <= x && x < W && 0 <= y && y < H;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int TC = Integer.parseInt(br.readLine());

        for(int tc=1; tc<=TC; tc++) {

            // read input
            StringTokenizer st = new StringTokenizer(br.readLine());
            H = Integer.parseInt(st.nextToken());
            W = Integer.parseInt(st.nextToken());

            arr = new char[H][W];
            V = new int[H][W];

            // find location
            ArrayDeque<int[]> Q = new ArrayDeque<>();
            int sx = 0, sy = 0, ex = 0, ey = 0, sdx = 0, sdy = 0;
            for(int y=0; y<H; y++) {
                arr[y] = br.readLine().toCharArray();
                Arrays.fill(V[y], -1);
                for(int x=0; x<W; x++) {
                    if(arr[y][x] == 'S') {
                        sx = x; sy = y;
                    } else if(arr[y][x] == 'D') {
                        ex = x; ey = y;
                    } else if(arr[y][x] == '*') {
                        sdx = x; sdy = y;
                        Q.offer(new int[]{sdx,sdy,0,0});
                    }
                }
            }

            // BFS
            V[sy][sx] = 0;
            Q.offer(new int[]{sx,sy,0,1});

            while(!Q.isEmpty()) {
                int[] cur = Q.pollFirst();
                int x = cur[0], y = cur[1], t = cur[2], player = cur[3];

                for(int[] dire : dires) {
                    int nx = x + dire[0], ny = y + dire[1];

                    if(!inside(nx,ny)) continue;

                    // player의 이동인 경우 . or D로 이동 가능
                    if(player == 1 && (arr[ny][nx] == '.' || arr[ny][nx] == 'D') && V[ny][nx] == -1) {
                        Q.offer(new int[]{nx,ny,t+1,1});
                        V[ny][nx] = t+1;

                    // devil의 이동인 경우 S or .로 이동
                    } else if(player == 0 && (arr[ny][nx] == 'S' || arr[ny][nx] == '.')) {
                        Q.offer(new int[]{nx,ny,t+1,0});
                        arr[ny][nx] = '*';
                    }
                }
            }

            String answer = V[ey][ex] == -1 ? "GAME OVER" : String.valueOf(V[ey][ex]);
            System.out.println("#" + tc + " " + answer);
        }
    }
}

코멘트

• .