14503 - 로봇 청소기[G5]

 

문제

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

 

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

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

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

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

입력

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

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

출력

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

 

풀이

주어진 조건에 맞는 시뮬레이션 코드.

특이하게도 경계선 바운더리를 항상 1로 보장해준다. 이때문에 맵을 벗어나는 조건은 구현하지 않아도 되긴 한다.

 

코드

 

import java.util.*;
import java.io.*;

public class Main {
	static int M, N;
	static int[] DR = {-1, 0, 1, 0}; //북동남서
	static int[] DC = {0, 1, 0, -1};
	static int[][] map;
	static boolean[][] visit;
	static int cnt = 0;
	
	static Pos robot;
	public static void main(String[] args) {
		input();
		while(true) {
			if(solve()) break;
		}
		System.out.println(cnt);
	}
	
	static boolean solve() {
		int r = robot.r;
		int c = robot.c;
		int d = robot.d;
		if(!visit[r][c]) {
			cnt++;
			visit[r][c] = true;
		}
		
		//빈 칸 존재하는지?
		if(check4Way(r, c)) {
			//반시계 회전
			if(d == 0) d = 3;
			else d -= 1;
			robot.d = d;
			//앞 칸이 갈 수 있는 청소x벽인지?
			int nr = r + DR[d];
			int nc = c + DC[d];
			if(!cantGo(nr, nc) && map[nr][nc] == 0 && !visit[nr][nc]) {
				robot.r = nr;
				robot.c = nc;
			}
			return false;
		} else { //빈 칸 없음
			int nr = r - DR[d];
			int nc = c - DC[d];
			if(cantGo(nr, nc) || map[nr][nc] == 1) return true; //이동 불가
			robot.setPos(nr, nc);
			return false;
		}
	}
	
	//빈 칸 존재하면 true
	static boolean check4Way(int r, int c) {
		for(int i = 0; i < 4; i++) {
			int nr = r + DR[i];
			int nc = c + DC[i];
			if(cantGo(nr, nc)) continue;
			if(map[nr][nc] == 0 && visit[nr][nc] == false) return true; //빈 칸 존재
		}
		return false;
	}
	
	static boolean cantGo(int r, int c) {
		return r < 0 || c < 0 || r >= N || c >= M;
	}
	
	static void input() {
		try {
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			StringTokenizer st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			st = new StringTokenizer(br.readLine());
			int r = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			int d = Integer.parseInt(st.nextToken());
			robot = new Pos(r, c, d);
			map = new int[N][M];
			visit = new boolean[N][M];
			
			for(int i = 0; i < N; i++) {
				st = new StringTokenizer(br.readLine());
				for(int j = 0; j < M; j++) {
					map[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			
		} catch(Exception e) {}
	}
}

class Pos {
	int r, c, d;
	
	public Pos(int r, int c, int d) {
		this.r = r;
		this.c = c;
		this.d = d;
	}
	
	public void setPos(int r, int c) {
		this.r = r;
		this.c = c;
	}
}