BOJ 14503 로봇 청소기

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

14503번: 로봇 청소기

 

 

문제 분석

- 청소기가 움직이는 순서 그대로 구현한다. 

 

 

문제 풀이

(코드 내 주석 참고-)

 

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

public class Main {

	private static int N, M, r, c, d, result;
	private static int[] dr = { -1, 0, 1, 0 };
	private static int[] dc = { 0, 1, 0, -1 }; // -> 0:북, 1:동, 2:남, 3:서
	private static int[][] map;

	public static void main(String[] args) throws IOException {
		input();
		solution();
		output();
	} // main 함수 종료

	private static void output() {
		System.out.println(result);
	} // output 함수 종료

	private static void solution() {
		// 1번
		if (map[r][c] == 0) { // 방향만 바꾸고 오는 경우 현재 칸을 처리하면 안되기때문에 if문으로 조건 추가
			map[r][c] = -1; // 청소한 위치는 -1로 표기
			result++; // 현재 영역 청소
		}

		// 2번
		int count = 0;
		for (int i = 0; i < 4; i++) {
			// 다음 방향, 장소 계산
			int nd = (d + 3) % 4; // d-1하면 다음 방향이니까 모듈러 연산 사용
			int nr = r + dr[nd];
			int nc = c + dc[nd];

			// a
			if (map[nr][nc] == 0) { // 만약 청소하지 않은 공간이 있다면
				d = nd; // 그 방향으로 회전
				r = nr; // 한 칸 전진
				c = nc; // 한 칸 전진
				solution(); // 1번부터 진행
			} else {
				// b
				d = nd; // 그 방향으로 회전하고
				// 2번으로 돌아간다.
				count++;
			}
		}

		// c
		// 네 방향 모두 청소가 이미 되었거나 벽인 경우
		if (count == 4) {
			// 후진할 수 있는 경우
			if (d == 0) {
				if (r + 1 >= 0 && r + 1 < N && map[r + 1][c] != 1) {
					r += 1;
					solution();
				}
			} else if (d == 1) {
				if (c - 1 >= 0 && c - 1 < M && map[r][c - 1] != 1) {
					c -= 1;
					solution();
				}
			} else if (d == 2) {
				if (r - 1 >= 0 && r - 1 < N && map[r - 1][c] != 1) {
					r -= 1;
					solution();
				}
			} else {
				if (c + 1 >= 0 && c + 1 < M && map[r][c + 1] != 1) {
					c += 1;
					solution();
				}
			}
			// d
			return;
		}

	} // input 함수 종료

	private static void input() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		map = new int[N][M];

		st = new StringTokenizer(br.readLine());
		r = Integer.parseInt(st.nextToken());
		c = Integer.parseInt(st.nextToken());
		d = Integer.parseInt(st.nextToken());

		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());
			}
		}
	} // input함수 종료

} // Class-End