[SWEA]7793번:오! 나의 여신님(JAVA)

 

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWsBQpPqMNMDFARG 

SW Expert Academy

---

• 알고리즘[풀이방법]

수연이가 악마의 손아귀를 피해 여신님이 계신 곳으로 이동해야하는 문제이다. 악마의 손아귀는 사방으로 이동하기 때문에 이를 표현해주기 위해 BFS를 이용하여 풀었다. 수연이가 여신님께 도달할 수 있는 최소 시간을 구해야하기 때문에 POINT안에  TIME변수를 설정해주고 한 턴이 끝날 때마다 1씩 증가해서 큐에 넣어준다.

악마의 큐와 수연이의 큐를 따로 설정한 후, 해당 TIME에서 각각 큐에 들어있는 값들이 돌맹이가 있는 지점('.')으로만 이동할 수 있게 했다. 악마를 먼저 이동시키고, 악마가 가지 않은 곳에 수연이가 이동할 수 있도록 하였다. 만약 수연이가 여신님을 만나게 되면 해당 time을 answer에 저장해주고 return한다. 반면, 수연이가 이동할 수 있는 곳이 없게 되면 수연이의 queue가 비게 되고, solve안에 있는 while문이 끝나게 된다. 이 경우 answer에 값이 담기지 않아 GAMEOVER를 출력하게 된다.

---

 

package 김영서;

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

public class Solution {
	static int N, M, answer, move[][];
	static char map[][];
	static Queue<Point> sq, dq;

	static void solve() {
		while (!sq.isEmpty()) {
        int d = dq.size();
        for (int j = 0; j < d; j++) {// 악마 사방탐색 -> 현재 악마가 움직일 수 있는만큼만 가기
            Point tmp = dq.poll();
            for (int i = 0; i < 4; i++) {
                int nr = tmp.r + move[i][0];
                int nc = tmp.c + move[i][1];
                if (nc >= 0 && nr < N && nr >= 0 && nc < M &&(map[nr][nc] == '.' || map[nr][nc] == 'S')) {
                    //System.out.println("D"+tmp.r + " " + tmp.c);
                    Point newP = new Point(nr, nc);
                    map[nr][nc] = '*';
                    dq.add(newP);
                }
            }
        } // 악마 for

        // 수연이가 이동할 수 있는 경로로 움직이기...!
        d = sq.size();
        for (int j = 0; j < d; j++) {
            Point tmp = sq.poll();
            for (int i = 0; i < 4; i++) {
                int nr = tmp.r + move[i][0];
                int nc = tmp.c + move[i][1];
                if (nc >= 0 && nr < N && nr >= 0 && nc < M && (map[nr][nc] == '.' || map[nr][nc] == 'D')) {						
//						System.out.println("S"+nr+" "+nc+" "+tmp.time);
                    Point newP = new Point(nr, nc, tmp.time+1);
                    if (map[newP.r][newP.c] == 'D') {// 여신님과 만났으면 빠져나가기?
                        answer = tmp.time;
                        return;
                    }
                    map[nr][nc]='S';
                    sq.add(newP);
                }
            }
        }
    }
	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		int T = Integer.parseInt(br.readLine());
		for (int tc = 1; tc <= T; tc++) {
			answer=0;
			int[] NM = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
			N = NM[0];
			M = NM[1];
			map = new char[N][M];
			move = new int[][] { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
			sq = new ArrayDeque<Point>();
			dq = new ArrayDeque<Point>();
			for (int i = 0; i < N; i++) {
				String str = br.readLine();
				for (int j = 0; j < M; j++) {
					map[i] = str.toCharArray();
					if (map[i][j] == 'S') {
						sq.add(new Point(i, j, 1));
					} else if (map[i][j] == '*') {
						dq.add(new Point(i, j));
					}
				}
			}
			// System.out.println(Arrays.deepToString(map));
			solve();
			if(answer==0) {
				System.out.println("#" + tc + " GAME OVER");				
			}else {					
				System.out.println("#" + tc + " " + answer);
			}
		}

	}

	static class Point {
		int r, c, time;
		public Point(int r, int c, int time) {
			super();
			this.r = r;
			this.c = c;
			this.time = time;
		}
		public Point(int r, int c) {
			super();
			this.r = r;
			this.c = c;
		}
	}

}