[백준] 3055번 탈출 (java, bfs)

www.acmicpc.net/problem/3055

3055번: 탈출

청소년 상어를 풀고나서 이 문제를 푸니 dfs가 익숙해서 dfs로 경우를 탐색하다가 메모리 초과가 났다.

 

가끔 bfs로만 되거나 dfs만 되는 문제들이 있어서 헷갈리는데 최단 시간 (같은 위치 구간에서 동시에 탐색할 때)는 bfs이고 모든 경우의 수를 다 돌아봐야하는 경우 (청소년 상어처럼 먹는 물고기 번호가 가장 큰것을 구하는 것)은 dfs인 것

같다. 

 

물이 차오를 지역도 못간다는 것은 즉, 물이 찬 것과 같다라는 뜻이라서 물을 먼저 채워버린 다음에 고슴도치가 

이동하면 된다. 

 

물이 한 번 차면 고슴도치의 큐의 현재 사이즈만큼 돌면서 다음 고슴도치가 갈 수 있는 장소들을 업데이트 해준 다음 

 

다시 물을 채우는 방식으로 하면 된다.

 

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class Pos{
	int y,x,time;
	
	public Pos(int y, int x) {
		super();
		this.y = y;
		this.x = x;
	}
	
	public Pos(int y, int x,int time) {
		super();
		this.y = y;
		this.x = x;
		this.time=time;
	}
}

public class Main {
	static int r,c;
	static int[] xpos= {0,0,1,-1};
	static int[] ypos= {1,-1,0,0};
	static int answer=Integer.MAX_VALUE;
	static char[][] map=new char[r][c];
	static Queue<Pos> q=new LinkedList<Pos>();
	static Queue<Pos> water=new LinkedList<>();
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		r=sc.nextInt();
		c=sc.nextInt();
		map=new char[r][c];
		for (int i = 0; i < r; i++) {
			String s=sc.next();
			for (int j = 0; j < c; j++) {
				map[i][j]=s.charAt(j);
				if(map[i][j]=='S') {
					q.add(new Pos(i,j,0));
				}else if(map[i][j]=='*') {
					water.add(new Pos(i,j));
				}
			}
		}
		
		go();
		
		System.out.println(answer==Integer.MAX_VALUE?"KAKTUS":answer);
		
		
	}
	private static void go() {
		
		while(q.size()!=0) {
			int len=water.size();
			//물 퍼뜨림
			for (int i = 0; i < len; i++) {
				Pos cur=water.poll();
				int y=cur.y;
				int x=cur.x;
				for (int k = 0; k < 4; k++) {
					int yy=y+ypos[k];
					int xx=x+xpos[k];
					if(xx<0 || yy<0 || xx>=c || yy>=r)continue;
					if(map[yy][xx]=='D' || map[yy][xx]=='X' || map[yy][xx]=='*')continue;
					map[yy][xx]='*';
					water.add(new Pos(yy,xx));
				}
				
			}
			
			len=q.size();
			for (int i = 0; i < len; i++) {
				// 고슴 도치 이동
				Pos cur=q.poll();
				int y=cur.y;
				int x=cur.x;
				int time=cur.time;
				for (int k = 0; k < 4; k++) {
					int yy=y+ypos[k];
					int xx=x+xpos[k];
					if(xx<0 || yy<0 || xx>=c || yy>=r)continue;
					if(map[yy][xx]=='D') {
						answer=Math.min(answer, time+1);
						return;
					}else if(map[yy][xx]=='.') {
						map[yy][xx]='S';
						q.add(new Pos(yy,xx,time+1));
					}
				}
			}
			

		}
		
	}
	
		
}