[백준] 3055. 탈출

https://www.acmicpc.net/problem/3055

3055번: 탈출

---

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	
	static class Obj {
		int x;
		int y;
		char val;
		
		public Obj(int x, int y, char val) {
			this.x = x;
			this.y = y;
			this.val = val;
		}		
	}
	
	static int R, C, TIME;
	static char[][] map;
	static Queue<Obj> queue = new LinkedList();
	static boolean[][] visited;
	static int[][] dir = {{1,0},{0,1},{-1,0},{0,-1}};
	static boolean flag = false;
	static ArrayList<Obj> list = new ArrayList();
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		R = sc.nextInt();
		C = sc.nextInt();
		
		map = new char[R][C];
		visited = new boolean[R][C];
		
		for(int i=0; i<R; i++) {
			String st = sc.next();
			for(int j=0; j<C; j++) {
				map[i][j] = st.charAt(j);
				if(map[i][j] == 'S') {
					list.add(new Obj(i, j, 'S'));
					visited[i][j] = true;
				} else if(map[i][j] == '*') {
					list.add(new Obj(i, j, '*'));
					visited[i][j] = true;
				}
			}
		}
		
		Collections.sort(list, new Comparator<Obj>() {
			@Override
			public int compare(Obj o1, Obj o2) {
				return Character.compare(o1.val, o2.val);
			}
		});
		
		for(Obj obj : list) {
			queue.offer(obj);
		}
		
		BFS();
		
		if(flag) {
			System.out.println(TIME);
		} else {
			System.out.println("KAKTUS");
		}
	}
	
	public static void BFS() {
		
		while(!queue.isEmpty()) {
			int len= queue.size();
			TIME++;
			
			for(int i=0; i<len; i++) {
				Obj obj = queue.poll();
				
				for(int j=0; j<4; j++) {
					int nx = obj.x + dir[j][0];
					int ny = obj.y + dir[j][1];
					
					if(isInside(nx, ny) && !visited[nx][ny]) {
						if(obj.val == 'S' && map[nx][ny] == 'D') {
							flag = true;
							return;
						} else if(obj.val == '*' && (map[nx][ny] == '.' || map[nx][ny] == 'S')) {
							map[nx][ny] = obj.val;
							visited[nx][ny] = true;
							queue.offer(new Obj(nx, ny, obj.val));
						} else if(obj.val == 'S' && map[nx][ny] == '.') {
							map[nx][ny] = obj.val;
							visited[nx][ny] = true;
							queue.offer(new Obj(nx, ny, obj.val));
						}
					}
				}
			}
		}
	}
	
	public static boolean isInside(int x, int y) {
		return x>=0 && x<R && y>=0 && y<C;
	}
}