SWEA - 오! 나의 여신님 JAVA

최소시간을 구해야하므로 bfs를 이용한다.

악마는 수연이와 빈 곳을 침범 가능 

수연이는 빈곳으로만 이동가능 

여신을 만났을때 종료!

 

package a0406;

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

/*
 악마의 손아귀를 피해서 최소시간에 여신에게 가야함 
 악마의 손아귀 -> 악마 위치 기준으로 1초마다 상하좌우로 퍼져나감 
 수연 -> 1초마다 상하좌우로 이동 가능 
 
 최소시간은?
 */

public class SWEA오나의여신님 {

	static char[][] arr;
	static int[][] visit;
	static int sero ;
	static int garo ;
	static int starti;	static int startj;
	static int angeli;	static int angelj;
	
	static int[] di = {-1, 0, 1, 0};
	static int[] dj = {0, 1, 0, -1};
	
	static boolean check(int i, int j) {
		if(0<=i&&i<sero && 0<=j&&j<garo)return true;
		return false;
	}
	
	static int findflag = 0;
	static int cannotflag = 0;
	
	static void bfs() {			// 수연이의 이동 
	
		Queue<int[]> q = new LinkedList<>();
		for(int i=0; i<sero; i++) {
			for(int j=0; j<garo; j++) {
				if(arr[i][j]=='S') {
					q.add(new int[] {i,j});
				}
			}
		}
		
		if(q.size()==0) {
			cannotflag = 1;
			return;
		}
		
		while(!q.isEmpty()) {
			
			int now[] = q.poll();
			int nowi = now[0];	int nowj = now[1];
			
			for(int d=0; d<4; d++) {
				int ni = nowi+di[d];
				int nj = nowj+dj[d];
				if(check(ni,nj) && visit[ni][nj]==0 && (arr[ni][nj]=='.' || arr[ni][nj]=='D')) {
					visit[ni][nj] = 1;
					if(arr[ni][nj] == 'D') {
						findflag = 1;
						break;
					}else arr[ni][nj] = 'S';
				}
			}
		}
	}
	
	static void devilmove() {
		Queue<int[]> devil = new LinkedList<>();
		for(int i=0; i<sero; i++) {
			for(int j=0; j<garo; j++) {
				if(arr[i][j]=='*') {
					devil.add(new int[] {i,j});
				}
			}
		}
		
		while(!devil.isEmpty()) {
			
			int now[] = devil.poll();
			int nowi = now[0];	int nowj = now[1];
			
			for(int d=0; d<4; d++) {
				int ni = nowi+di[d];
				int nj = nowj+dj[d];
				if(check(ni,nj) && (arr[ni][nj]=='.' || arr[ni][nj]=='S')) {
					arr[ni][nj] = '*';
				}
			}
		}
	}
	
	static void print() {
		for(int i=0; i<sero; i++) {
			for(int j=0; j<garo; j++) {
				System.out.print(arr[i][j]+" ");
			}
			System.out.println();
		}
		System.out.println();
	}
	
	public static void main(String[] args) throws Exception{

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int tc = Integer.parseInt(br.readLine());
		
		for(int t=1; t<=tc; t++) {
			StringTokenizer ST = new StringTokenizer(br.readLine());
			sero = Integer.parseInt(ST.nextToken());
			garo = Integer.parseInt(ST.nextToken());
			
			arr = new char[sero][garo];
			visit = new int[sero][garo];
			
			for(int i=0; i<sero; i++) {					//입력 
				String st = br.readLine();
				for(int j=0; j<garo; j++) {
					arr[i][j] = st.charAt(j);
				}
			}
			int cnt =0;
			findflag = 0;
			cannotflag = 0;
//			bfs();
//			print();
//			
//			devilmove();
//			print();
//			
			while(true) {
				cnt++;
				bfs();
				print();
				if(findflag==1)break;
				if(cannotflag==1)break;
				devilmove();	
				print();
			}
			System.out.print("#"+t+" ");
			
			if(cannotflag == 0)System.out.println(cnt);
			else System.out.println("GAME OVER");
		
		}
	}
}