[백준 31404] 아리스, 청소합니다! (Easy) - JAVA

문제 링크

오늘 solved.ac에 접속해보면
스팸 사이트 같이 나와서 놀랐는데
생각해보니 만우절이였습니다 ㅎㅎ..

이 중 하나를 선택했더니 해당 문제가 나와서 풀게 되었습니다.

문제 정의

• `$H * W$ 크기의 방이 존재
• 처음에는 각 방마다 먼지로 뒤덮임
• 각 공간마다 규칙표 $A$, 규칙표 $B$가 존재 $H *W$의 입력으로 주어짐
• 로봇 청소기는 매 단위 시간마다 다음과 같은 이동을 반복
  • 현재 칸에 먼지가 있다면 제거
  • 방금 먼지를 제거했다면 규칙표 $A$를, 먼지를 제거하지 않았다면 규칙표 $B$를 참조
  • 바라보는 방향으로 한 칸 전진
• 이동을 마친 후
  • 로봇 청소기가 영역 밖으로 벗어났다면 작동을 중지
• 지금부터 위의 과정을 아무리 반복해도 더이상 먼지를 제거할 수 없는 경우에도 작동을 중지

---

예시

아리스는 아래 그림과 같은 순서로 이동합니다.

아리스가 $13$회 이동하고 나면,
더이상 이동을 반복해도 계속해서 먼지가 없는 칸만 방문하므로 청소를 중지합니다.

---

접근 방법

지시사항에 맞게 메서드를 구현하고
한 칸씩 이동하면서 체킹하는 심플한 코드를 구현했습니다.

while문을 사용해 계속해서 3가지 조건에 의해 반복되며
2가지 종료 조건에 의해 로직이 종료되도록 구현했습니다.

---

outbound 처리

이동을 방의 범위 밖으로 했다면
청소를 중지해야하는데 상황에 이동 횟수가 다릅니다.

이동 전에 먼지를 청소한 경우

이전 이동에 의미가 있었기 때문에 현재까지 움직인 횟수를 반환합니다.

이동 전에 먼지를 청소하지 않은 경우

이전 이동에 의미가 없는 경우이기 때문에
의미있는 이동 횟수를 저장한 save - 1을 반환합니다.

---

의미있는 이동 정하기

의미있는 이동이 되려면
가장 우선적으로는 이번 회차에 먼지를 치운 경우가 되어야 합니다.

isCleaning 변수로
청소했는지 여부를 판단해
의미있는 이동이었다면 save에 현재까지의 이동 moves를 제공합니다.

이번에 청소를 하지 않았다고 모두 의미없는 이동일까?

아닙니다.

특정 위치에 특정 방향으로 몇 번이던 도달하더라도
의미있는 이동이 될 수 있습니다.

그것을 정하는 것은
사이클 도중에 save가 변했는지를 보면 됩니다.

사이클 도중 save가 변하지 않았다면
의미없는 사이클로 간주해서 종료합니다.

---

코드

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

public class Main {
	static StringTokenizer st;
	static int H;
	static int W;
	static int R;
	static int C;
	static int D;
	static int[][] ruleA;
	static int[][] ruleB;
	static int[][][] visited;
	static boolean[][] isNotDust;
	static int[] dy = {-1, 0, 1, 0};
	static int[] dx = {0, 1, 0, -1};

	static void init() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		st = new StringTokenizer(br.readLine());
		H = Integer.parseInt(st.nextToken());
		W = Integer.parseInt(st.nextToken());
		isNotDust = new boolean[H][W];

		st = new StringTokenizer(br.readLine());
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		D = Integer.parseInt(st.nextToken());
		visited = new int[H][W][4];

		ruleA = new int[H][W];
		ruleB = new int[H][W];

		fillArray(ruleA, br);
		fillArray(ruleB, br);
	}

	static void fillArray(int[][] rule, BufferedReader br) throws IOException {
		for (int i = 0; i < H; i++) {
			int j = 0;
			for (char c : br.readLine().toCharArray()) {
				rule[i][j] = c - 48;
				j++;
			}
		}
	}

	static int doCleanAris() {
		int moves = 1;
		int save = 1;
		while (true) {
			if (visited[R][C][D] == save) {
				return save - 1;
			}
			
			visited[R][C][D] = save;
			boolean isCleaning = false;
			
			if (!isNotDust[R][C]) {
				isNotDust[R][C] = true;
				isCleaning = true;
			}

			D = (D + (isCleaning ? ruleA[R][C] : ruleB[R][C])) % 4;
			R += dy[D];
			C += dx[D];

			if (outbound()) {
				return isCleaning ? moves : save - 1;
			}

			moves++;
			
			if (isCleaning) {
				save = moves;
			}
		}
	}

	static boolean outbound() {
		return R < 0 || R >= H || C < 0 || C >= W;
	}

	public static void main(String[] args) throws IOException {
		init();
		System.out.println(doCleanAris());
	}
}