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

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

SW Expert Academy

악마큐, 수연큐 두 개를 만들어서 큐사이즈만큼 bfs를 돌려줬다.

테스트케이스 10개중 6개만 맞았다고 떠서 틀린 거 찾느라 고생했다.ㅠㅠ

while문 종료조건을 수연큐가 비면 종료로 했어야했는데 악마큐로 잘못 썼었다..

큐를 두개 이상 사용할 때는 주의해서 짜자^^......

 

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.StringTokenizer;

class Point{
	int x;
	int y;
	public Point(int x, int y) {
		super();
		this.x = x;
		this.y = y;
	}
	
}
public class Solution {

	static int N,M,ans;
	static char[][] map;
	static boolean[][][] visit;
	static int[] dx= {0,0,1,-1};
	static int[] dy= {1,-1,0,0};
	
	public static void main(String[] args) throws Exception{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int T=Integer.parseInt(br.readLine());
		for(int tc=1; tc<=T; tc++) {
			ans=-1;
			Queue<Point> devil=new LinkedList<Point>();
			Queue<Point> su=new LinkedList<Point>();
			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][2];
			for(int i=0; i<N; i++) {
				String s=br.readLine();
				for(int j=0; j<M; j++) {
					map[i][j]=s.charAt(j);
					if(map[i][j]=='*') {
						visit[i][j][0]=true;
						devil.offer(new Point(i,j));
					}
					if(map[i][j]=='S') {
						visit[i][j][1]=true;
						su.offer(new Point(i,j));
					}
				}
			}
			
			int cnt=0;
			loop:
			while(true) {
				int dSize=devil.size();
				int sSize=su.size();
				if(sSize==0)break;
				while(dSize-->0) {
					Point p=devil.poll();
					for(int i=0; i<4; i++) {
						int nx=p.x+dx[i];
						int ny=p.y+dy[i];
						if(nx<0||ny<0||nx>=N||ny>=M||
								map[nx][ny]=='D' ||visit[nx][ny][0]==true ||map[nx][ny]=='X')
							continue;
						visit[nx][ny][0]=true;
						map[nx][ny]='*';
						devil.offer(new Point(nx,ny));
					}
				}
				while(sSize-->0) {
					Point p=su.poll();
					if(map[p.x][p.y]=='D') {
						ans=cnt;
						break loop;
					}
					for(int i=0; i<4; i++) {
						int nx=p.x+dx[i];
						int ny=p.y+dy[i];
						if(nx<0||ny<0||nx>=N||ny>=M||
								map[nx][ny]=='*' ||visit[nx][ny][1]==true ||map[nx][ny]=='X')
							continue;
						
						visit[nx][ny][1]=true;
						su.offer(new Point(nx,ny));
					}
				}
				cnt++;
			}
			System.out.println("#"+tc+" "+(ans==-1? "GAME OVER":ans));
			
		}
	}
	

}