[KOITP] 유령선

출    처 : http://koitp.org/problem/SDS_PRO_4_1/read/

시간 제한	메모리 제한	제출 횟수	정답 횟수 (비율)	정답자 수
1.0 초	512 MB	2193	378 (17%)	323

문제

강희는 정신을 차려보니 낯선 유령선에 납치당해 있었다. 강희는 유령들이 자고 있는 낮 시간에 몰래 유령선에 있는 구명보트를 이용해 탈출하려고 한다.

유령선의 갑판은 동일한 크기의 정사각형 모양 판자가 가로로 W개, 세로로 H개 이어진 모양으로 되어 있다. 강희는 현재 서 있는 위치에서 상하좌우로 움직일 수 있다. 유령선은 매우 낡았기 때문에 강희가 딛고 있는 판자를 벗어나면 판자가 부서지고 만다. 심지어 이미 부서져 있는 판자도 존재한다. 물론 강희는 유령이 아니기 때문에 부서진 판자는 걸어서 지나갈 수 없다.

판자가 너무 많이 부서지면 유령들이 화를 내기 때문에 강희는 가장 작은 개수의 판자를 파괴하면서 유령선에서 탈출하려고 한다. 강희가 유령선에서 탈출하는 것을 돕는 프로그램을 작성하자.

시간제한: 1초

입력

첫 줄에 두 정수 W(2<=W<=1500)와 H(2<=H<=1500)가 공백을 사이에 두고 주어진다. 그 다음 줄부터 H줄마다 각각 W개의 문자가 주어진다.

각 문자는 X, O, S, E 중 하나며 전체 문자들 중 S와 E는 정확히 하나임이 보장된다.

• X는 처음부터 부서진 판자를 나타낸다.
• O는 강희가 밟고 지나갈 수 있지만, 밟은 이후 부서지는 판자를 나타낸다.
• S는 처음 강희가 서 있는 판자의 위치를 나타낸다.
• E는 유령선의 구명보트 위치를 나타낸다.

출력

강희가 판자를 최소 개수로 파괴하면서 유령선에서 탈출할 때 파괴되는 판자의 개수를 첫 줄에 출력하라.

만약 강희가 유령선에서 탈출할 수 있는 방법이 없는 경우, -1을 출력하라.

힌트

예제 입력 1

4 3
OOSO
OXXO
OOEO

예제 출력 1

4

예제 설명 1

총 두 가지 탈출 경로가 존재한다.

강희가 (좌, 좌, 하, 하, 우, 우)로 움직이는 경우 6개의 판자가 부서진다.

강희가 (우, 하, 하, 좌)로 움직이는 경우 4개의 판자가 부서진다.

따라서 답은 4이다.

---

예제 입력 2

3 3
EXX
XSO
OOX

예제 출력 2

-1

< Comment >

 단순한 BFS 문제인데, 그럼에도 불구하고 예외처리를 확실히 해주지 못하는 바람에 오랜 시간이 걸렸습니다. 다른 것은 아니었고, 익셉션이 발생하던 이유는 제가 리턴 값을 count 로 주어야하는데, 이를 계속 큐에 들어있는 노드의 마지막 값으로 출력하려고 했기 때문에 생긴 문제였습니다. 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayDeque;
import java.util.StringTokenizer;

public class Spector {
	
	public static int W = 0;
	public static int H = 0;
	
	public static char[][] map = null;
	public static boolean[][] isVisited = null;
	
	public static int[] dx = {1, -1, 0, 0};
	public static int[] dy = {0, 0, 1, -1};
	
	public static class Node {
		
		int x = 0;
		int y = 0;
		int depth = 0;
		
		public Node(int x, int y, int depth) {
			this.x = x;
			this.y = y;
			this.depth = depth;
		}
		
		public int getX() {
			return x;
		}
		
		public int getY() {
			return y;
		}
		
		public int getDepth() {
			return depth;
		}
	}

	public static void main(String[] args) throws Exception {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		W = Integer.parseInt(st.nextToken());
		H = Integer.parseInt(st.nextToken());
		
		map = new char[H][W];
		isVisited = new boolean[H][W];
		
		String strLine = "";
		int startx = 0;
		int starty = 0;
		for (int i = 0 ; i < H ; i++) {
			
			strLine = br.readLine();
			for (int j = 0 ; j < W ; j ++) {
				
				map[i][j] = strLine.charAt(j);
				if (map[i][j] == 'S') {
					startx = i;
					starty = j;
				}
			}
		}
		
		int result = BFS(startx, starty);
		bw.write("" + result);
		bw.flush();
		bw.close();
	}
	
	public static int BFS (int x, int y) {
		
		ArrayDeque<Node> dq = new ArrayDeque<>();
		dq.addLast(new Node(x, y, 0));

		while(!dq.isEmpty()) {
			
			Node node = dq.pollFirst();
			int count = node.getDepth();
			if(isVisited[node.getX()][node.getY()])	continue;
			
			int nodeX = node.getX();
			int nodeY = node.getY();
			
			isVisited[nodeX][nodeY] = true;
			for (int i = 0 ; i < 4 ; i++) {
				
				int nx = nodeX + dx[i];
				int ny = nodeY + dy[i];
				
				if (nx < H && nx >= 0 && ny < W && ny >= 0) {
					
					if (map[nx][ny] == 'O') {
						dq.addLast(new Node(nx, ny, count + 1));
					} else if (map[nx][ny] == 'E') {
						return dq.isEmpty() ? 1 : count + 1;
					}
				}
			}
		}
		
		return -1;	
	}
}