[백준] 3055 - 탈출

[문제링크]

3055번: 탈출

 

0. 물이 찰 예정인 칸으로 진행할 수 없다 -> 물을 먼저 채우고 고슴도치를 이동시키면 된다

  - 고슴도치는 변수로 적절하지 않으니 대신 뜨또를 변수로 사용하였다.

 

1. 물 한번 - 고슴도치 한번 번갈아가며 빈 칸을 채우는 BFS 실행

  - ans가 갱신된 그 순간이 곧 최소시간이므로 즉시 탈출한다

  - 끝까지 갱신되지 못했다면 정해진 문자열 출력

 

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

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int n = pint(st.nextToken());
		int m = pint(st.nextToken());
		char[][]map=new char[n+2][m+2];
		for (int i = 0; i < m+2; i++) {
			map[0][i]='X';
			map[n+1][i]='X';
		}for (int i = 0; i < n+2; i++) {
			map[i][0]='X';
			map[i][m+1]='X';
		}
		
		Queue<int[]>bieber=new LinkedList<>();
		Queue<int[]>water=new LinkedList<>();
		
		for (int i = 1; i < n+1; i++) {
			String s = br.readLine();
			for (int j = 1; j < m+1; j++) {
				map[i][j]=s.charAt(j-1);
				if(map[i][j]=='S')bieber.offer(new int[] {i,j});
				if(map[i][j]=='*')water.offer(new int[] {i,j});
			}
		}

		int time=0, ans=-1;
		while(!bieber.isEmpty()) {
			time++;
			int len = water.size();
			//1. 물부터 진행,
			for (int i = 0; i < len; i++) {
				int[] cur=water.poll();
				
				for (int j = 0; j < 4; j++) {
					int tx=cur[0]+dx[j], ty=cur[1]+dy[j];
					if(tx<1||tx>n||ty<1||ty>m)continue;
					
					if(map[tx][ty]=='S'||map[tx][ty]=='.') {
						map[tx][ty]='*';
						water.offer(new int[] {tx,ty});
					}
					
				}
			}
			
			//2. 뜨또 진행
			len = bieber.size();
			for (int i = 0; i < len; i++) {
				int[] cur=bieber.poll();

				for (int j = 0; j < 4; j++) {
					int tx=cur[0]+dx[j], ty=cur[1]+dy[j];
					if(tx<1||tx>n||ty<1||ty>m)continue;
					
					if(map[tx][ty]=='.') {
						map[tx][ty]='S';
						bieber.offer(new int[] {tx,ty});
					}
					else if(map[tx][ty]=='D') {
						ans=time;
					}
				}
				
			}
			if(ans!=-1)break;
			
		}
		if(ans==-1)System.out.println("KAKTUS");
		else System.out.println(ans);
	}
	
	static int[]dx = {1,0,-1,0};
	static int[]dy = {0,1,0,-1};
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면