/ BOJ

BOJ_14503_로봇청소기_JAVA

문제 : 로봇청소기

링크 : BOJ_14503_로봇청소기

접근 방식

꽤 복잡하게 보이는 시뮬레이션 문제였다. 로봇청소기가 바라보고 있는 방향에 따라 왼쪽이 의미하는 방향이 각각 다르다는 점을 주의할 필요가 있다.

또한 4방향으로 회전을 모두 진행한 후에 후진을 할 때, 방향 전환 없이 현재 보고있는 방향에서 뒤로 1칸 움직여줘야 한다는 점도 생각해야한다.

몇 가지 신경써야하는 점을 제외하면 지시대로만 코드를 짜도 풀 수 있는 문제이다.

소스 코드

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

public class BOJ_14503_로봇청소기 {

	public static class Cleaner {
		int x;
		int y;
		int direction;

		public Cleaner(int x, int y, int direction) {
			super();
			this.x = x;
			this.y = y;
			this.direction = direction;
		}

	}

	static int N, M, ans, arr[][];

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

	public static void main(String[] args) throws IOException {

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(in.readLine(), " ");

		N = Integer.parseInt(st.nextToken());

		M = Integer.parseInt(st.nextToken());

		arr = new int[N][M];

		// 0 = 위, 1 = 오른, 2 = 아래, 3 = 왼
		st = new StringTokenizer(in.readLine(), " ");
		int x = Integer.parseInt(st.nextToken());
		int y = Integer.parseInt(st.nextToken());
		int direction = Integer.parseInt(st.nextToken());

		Cleaner cleaner = new Cleaner(x, y, direction);

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(in.readLine(), " ");
			for (int j = 0; j < M; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		move(cleaner);

		System.out.println(ans);

	}

	/*
	 * 현재 위치에서 왼쪽에 아직 청소하지 않은 빈 공간이 있다면 회전 후 전진 청소하지 않은 빈 공간이 없다면 회전만 함 회전을 4번하고 나면
	 * 뒤로 1칸 후진, 뒤가 벽이라면 종료
	 */
	public static void move(Cleaner cleaner) {
		boolean[][] visited = new boolean[N][M];
		// 초기위치 설정 및 청소
		visited[cleaner.x][cleaner.y] = true;
		ans++;
		// 회전 횟수를 체크할 변수
		int cnt = 0;
		while (true) {
			// 0일경우 3으로, 0이 아닐경우 -1시켜준다. : 로봇청소기 회전
			cleaner.direction = cleaner.direction == 0 ? cleaner.direction = 3 : cleaner.direction - 1;
			int vec = cleaner.direction;
			int dx = cleaner.x + dir[vec][0];
			int dy = cleaner.y + dir[vec][1];

			// 카운트가 4일 경우 뒤로 한 칸 이동
			if (cnt == 4) {
				// 처음 회전시킨 부분 원래 회전으로 한 번 돌리기
				cleaner.direction = cleaner.direction == 3 ? cleaner.direction = 0 : cleaner.direction + 1;
				vec = cleaner.direction;
				// 후진 위치
				dx = cleaner.x - dir[vec][0];
				dy = cleaner.y - dir[vec][1];

				// 만약 뒤가 벽이라면 종료
				if (arr[dx][dy] == 1) {
					return;
				}

				// 뒤가 벽이 아니라면 1칸 후진
				cleaner.x = dx;
				cleaner.y = dy;
				cnt = 0;
				continue;
			}

			// 이동 못하는 경우 컨티뉴, 카운트 1 증가
			if (arr[dx][dy] == 1 || visited[dx][dy] == true) {
				cnt++;
				continue;
			}

			// 이동할 수 있는 경우
			cleaner.x = dx;
			cleaner.y = dy;
			visited[dx][dy] = true;
			cnt = 0;
			ans++;
		}

	}

}

풀이 방법

  1. line 8 ~ 20 : 탐색을 할 때 사용할 좌표값과 방향을 가지고 있는 객체를 생성할 청소기 클래스이다.

  2. line 22 ~ 24 : 멤버 변수 선언부, 방향벡터를 2차원 배열로 선언해두었다.

  3. line 28 ~ 51 : 입력값을 받아 각각의 변수, 배열에 할당해 주는 구간이다. 이 시점에 청소기의 위치, 방향을 입력받아 객체를 생성한다.

  4. line 53 : 탐색 메서드 호출

  5. line 63 ~ 112 : 탐색 메서드 내부이다.

  6. line 64 ~ 69 : 초기 위치를 설정하고, 현재 위치를 청소 처리한다.

  7. line 70 ~ 110 : 로봇청소기가 종료되기까지 반복하는 반복문이다. 종료조건은, 4번의 회전을 했음에도 더 이상 청소할 수 있는 곳이 없고, 그 방향의 1칸 뒤가 벽일 경우이다.

  8. line 72 ~ 75 : 로봇청소기의 방향을 왼쪽으로 1번 회전시킨 후, 그 바로 한 칸 앞을 살펴보도록 좌표를 설정한다.

  9. line 78 ~ 96 : 4번 회전을 진행했음에도 움직일 수 없는 경우 처음 바라보던 방향으로 로봇청소기를 회전시킨 후 뒤로 한 칸 이동하는 로직이다. 만약 뒤에 벽이 있어서 움직일 수 없다면 return한다.(메서드 빠져나오기)

  10. line 99 ~ 102 : 한 번 회전할 때 해당 위치로 이동할 수 없는 경우 카운트를 1 증가시킨다. 이 값이 4가 되면 78 line의 로직이 수행된다.

  11. line 105 ~ 109 이동할 수 있는 경우에는, 움직였으므로 카운트를 초기화시켜주고, 이동한 위치를 방문처리한다. 추가로 청소한 횟수(ans)를 1 증가시킨다.

  12. line 55 : 모든 탐색이 종료된 후 청소한 횟수를 출력한다.