오 나의 여신님 [SWEA 7793][D5][Java]

 

[광고 누르면 오늘의 행운 상승!!]

 

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWsBQpPqMNMDFARG&categoryId=AWsBQpPqMNMDFARG&categoryType=CODE

SW Expert Academy

문제의 저작권은 SW Expert Academy에 있습니다.

??? 뭐지 방금 불 풀었는데

불 (백준5427) 이랑 똑같은 문제다. 

다른점이 있다면 맵 밖으로 나가냐 여신의 구역으로 이동하냐의 차이이다.

1. 큐를 두개 사용하여 악마의 손아귀와 사람의 위치를 각각 담는다.

2. 악마의 손아귀 큐의 갯수만큼 퍼져나가게 한다.

3. 사람의 큐 갯수 만큼 이동하게 하면서 cnt를 갱신한다

4. 여신의 구역으로 이동하면 cnt을 반환한다.

5. 이동하지 못하면 GAME OVER을 출력한다.

package Study0307;

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

class Position{
	int row, col, cnt;
	public Position(int row, int col,int cnt) {
		this.row = row;
		this.col = col;
		this.cnt = cnt;
	}
	public Position(int row, int col) {
		this.row = row;
		this.col = col;
	}
}
public class 오나의여신님 {
	public static final int[] dx = {1,0,-1,0};
	public static final int[] dy = {0,1,0,-1};
	public static int N,M,ans;
	public static boolean[][] visit;
	public static char[][] map;
	public static Queue<Position> q;
	public static Queue<Position> Devilq;
	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("test.txt"));
		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; tc++) {
			st = new StringTokenizer(br.readLine());
			
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			
			map = new char[N][M];
			visit = new boolean[N][M];
			q = new LinkedList<>();
			Devilq = new LinkedList<>();
			
			for (int i = 0; i < N; i++) {
				char[] ch = br.readLine().toCharArray();
				for (int j = 0; j < M; j++) {
					map[i][j] = ch[j];
					if		(map[i][j] == '*') Devilq.add(new Position(i,j));
					else if (map[i][j] == 'S') q.add(new Position(i,j,0));
				}
			}
			ans = 0;
			bfs();
			if(ans == 0) System.out.println("#" + tc + " " + "GAME OVER");
			else  	     System.out.println("#" + tc + " " + ans);
		}
	}
	public static void bfs() {
		
		int size = 0;
		while(!q.isEmpty()) {
			size = Devilq.size();
			for (int f = 0; f < size; f++) {
				Position devil = Devilq.poll();
				for (int i = 0; i < 4; i++) {
					int nx = devil.row + dx[i];
					int ny = devil.col + dy[i];
					
					if((nx<0 || nx >=N || ny <0 || ny>= M)) {
						continue;
					}
					
					if(map[nx][ny] == '.' || map[nx][ny] == 'S') {
						map[nx][ny] = '*';
						Devilq.add(new Position(nx,ny));
					}
				}
			}
			size = q.size();
			for (int h = 0; h < size; h++) {
				Position pos = q.poll();
				for (int i = 0; i < 4; i++) {
					int nx = pos.row + dx[i];
					int ny = pos.col + dy[i];
					
					if((nx<0 || nx >=N || ny <0 || ny>= M)) {
						continue;
					}
					if(map[nx][ny] == 'D') {
						ans = pos.cnt+1;
						return;
					}
					
					if(map[nx][ny] == '.') {
						map[nx][ny] = 'S';
						q.add(new Position(nx,ny,pos.cnt+1));
					}
				}
			}
		}
	}
}