문제

로봇 청소기와 방의 상태가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오.

로봇 청소기가 있는 방은
$N \times M$ 크기의 직사각형으로 나타낼 수 있으며,
$1 \times 1$ 크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북 중 하나이다. 방의 각 칸은 좌표
$(r, c)$로 나타낼 수 있고, 가장 북쪽 줄의 가장 서쪽 칸의 좌표가
$(0, 0)$, 가장 남쪽 줄의 가장 동쪽 칸의 좌표가
$(N-1, M-1)$이다. 즉, 좌표
$(r, c)$는 북쪽에서
$(r+1)$번째에 있는 줄의 서쪽에서
$(c+1)$번째 칸을 가리킨다. 처음에 빈 칸은 전부 청소되지 않은 상태이다.

로봇 청소기는 다음과 같이 작동한다.

현재 칸이 아직 청소되지 않은 경우, 현재 칸을 청소한다.
현재 칸의 주변
$4$칸 중 청소되지 않은 빈 칸이 없는 경우,
바라보는 방향을 유지한 채로 한 칸 후진할 수 있다면 한 칸 후진하고 1번으로 돌아간다.
바라보는 방향의 뒤쪽 칸이 벽이라 후진할 수 없다면 작동을 멈춘다.
현재 칸의 주변
$4$칸 중 청소되지 않은 빈 칸이 있는 경우,
반시계 방향으로
$90^\circ$ 회전한다.
바라보는 방향을 기준으로 앞쪽 칸이 청소되지 않은 빈 칸인 경우 한 칸 전진한다.
1번으로 돌아간다.

입력

첫째 줄에 방의 크기
$N$과
$M$이 입력된다.
$(3 \le N, M \le 50)$  둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표
$(r, c)$와 처음에 로봇 청소기가 바라보는 방향
$d$가 입력된다.
$d$가
$0$인 경우 북쪽,
$1$인 경우 동쪽,
$2$인 경우 남쪽,
$3$인 경우 서쪽을 바라보고 있는 것이다.

셋째 줄부터
$N$개의 줄에 각 장소의 상태를 나타내는
$N \times M$개의 값이 한 줄에
$M$개씩 입력된다.
$i$번째 줄의
$j$번째 값은 칸
$(i, j)$의 상태를 나타내며, 이 값이
$0$인 경우
$(i, j)$가 청소되지 않은 빈 칸이고,
$1$인 경우
$(i, j)$에 벽이 있는 것이다. 방의 가장 북쪽, 가장 남쪽, 가장 서쪽, 가장 동쪽 줄 중 하나 이상에 위치한 모든 칸에는 벽이 있다. 로봇 청소기가 있는 칸은 항상 빈 칸이다.

출력

로봇 청소기가 작동을 시작한 후 작동을 멈출 때까지 청소하는 칸의 개수를 출력한다.

예제1 - 입력

3 3
1 1 0
1 1 1
1 0 1
1 1 1

예제1 - 출력

1

예제2 - 입력

11 10
7 4 0
1 1 1 1 1 1 1 1 1 1
1 0 0 0 0 0 0 0 0 1
1 0 0 0 1 1 1 1 0 1
1 0 0 1 1 0 0 0 0 1
1 0 1 1 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 1 0 1
1 0 0 0 0 0 1 1 0 1
1 0 0 0 0 0 1 1 0 1
1 0 0 0 0 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1

예제2 - 출력

57

제출 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main{
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		
		st = new StringTokenizer(br.readLine());
		int x = Integer.parseInt(st.nextToken());
		int y = Integer.parseInt(st.nextToken());
		int d = Integer.parseInt(st.nextToken());
		
		Pair now = new Pair(x, y);
		
		boolean[][] map = new boolean[n][m];
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < m; j++) {
				char c = st.nextToken().charAt(0);
				map[i][j] = c == '0' ? false : true;
			}
		}
		
		boolean[][] cleaned = new boolean[n][m];
		
		int[] mx = {-1, 0, 1, 0};
		int[] my = {0, 1, 0, -1};
		
		int cnt = 0;
		while (true) {
			if (!cleaned[now.x][now.y]) {
				cnt++;
				cleaned[now.x][now.y] = true;
			}
			
			boolean check = false;
			for (int i = 0; i < mx.length; i++) {
				int tx = now.x + mx[i];
				int ty = now.y + my[i];
				
				if (tx < 0 || tx >= n || ty < 0 || ty >= m)
					continue;
				
				if (!map[tx][ty] && !cleaned[tx][ty]) {
					check = true;
					break;
				}
			}
			
			if (!check) {
				int tx = now.x - mx[d];
				int ty = now.y - my[d];
				
				if (tx < 0 || tx >= n || ty < 0 || ty >= m) {
					break;
				}
				else if (map[tx][ty])
					break;
				else {
					now = new Pair(tx, ty);
				}
			}
			
			else if (check) {
				if (--d < 0)
					d = 3;
				int tx = now.x + mx[d];
				int ty = now.y + my[d];
				
				if (tx < 0 || tx >= n || ty < 0 || ty >= m) 
					continue;
				else if (map[tx][ty])
					continue;
				else if (!cleaned[tx][ty]) {
					now = new Pair(tx, ty);
				}
			}
		}
		System.out.println(cnt);
	}
	static class Pair {
		public int x;
		public int y;
		public Pair(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
}