백준 14503 : 로봇 청소기

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

14503번: 로봇 청소기

[ 문제풀이 ]

간단한 시뮬레이션 문제이다. 주어진 조건 그대로 로봇을 움직이도록 구현하면 쉽게 해결할 수 있을 것이다.

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

public class Main {

	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static StringTokenizer st;

	static int N, M, answer;
	static int[][] map;
	static Robot robot;

	static int[][] dir = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

	static class Robot {
		int y, x, direct;

		public Robot(int y, int x, int direct) {
			this.y = y;
			this.x = x;
			this.direct = direct;
		}
	}

	public static void main(String[] args) throws IOException {
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		st = new StringTokenizer(br.readLine());
		int y = Integer.parseInt(st.nextToken());
		int x = Integer.parseInt(st.nextToken());
		int direct = Integer.parseInt(st.nextToken());
		robot = new Robot(y, x, direct);

		map = new int[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());
			}
		}

		simulation();
		bw.write(answer + "\n");
		bw.flush();bw.close();br.close();
	}

	public static void simulation() {
		//1. 현재 위치를 청소한다.
		if (map[robot.y][robot.x] == 0) {
			answer++;
			map[robot.y][robot.x] = 2;
		}
		
		//2. 현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다.
		for (int i = 1; i <= 4; ++i) {
			int next_Direct = (4 + robot.direct - i) % 4;
			int ny = robot.y + dir[next_Direct][0];
			int nx = robot.x + dir[next_Direct][1];

			//a. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.
			if (map[ny][nx] == 0) {
				robot.direct = next_Direct;
				robot.y = ny;
				robot.x = nx;

				simulation();
				return;
			}

			//b. 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.
		}

		//c. 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.
		robot.y -= dir[robot.direct][0];
		robot.x -= dir[robot.direct][1];
		
		//d. 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.
		if (map[robot.y][robot.x] == 1) return;
		
		simulation();
	}
}