[백준] 14503번 로봇 청소기 (자바)

난이도 ➜ 골드 5

주요 알고리즘 ➜ 구현

백준 14503번: 로봇 청소기 [Click]

✔️ 풀이

개인적으로는 안푸는 것을 추천
내 머리로는 문제가 굉장히 이해하기 힘들다.
예제를 보면 알 수 있지만 배열이 (0, 0) 부터 시작한다는 내용도 빠져 있고 무엇보다 나는 아래 조건들이 굉장히 헷갈린다 😳

간단히 정리하자면

• 현재 있는 칸 0라면 청소

• 4방향 중 왼쪽으로 회전하며 청소할 수 있는 칸이 존재 🟢

  • 전진

• 4방향 중 왼쪽으로 회전하며 청소할 수 있는 칸이 존재 ❌

  • 방향 유지한 채로 후진 여부 체크
    • 벽이라면 끝!!
    • 이미 청소한 칸이라면 후진 가능!

• 로봇 청소기는 이미 청소되어 있는 칸을 또 청소하지 않는다고 했기 떄문에 갈수는 있지만 갯수만 안늘려주면 된다.

✔️ 코드

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

public class Main {
    static int[] dr = {-1, 0, 1, 0};
    static int[] dc = {0, 1, 0, -1};
    static int N, M, R, C, D;
    static int[][] map;
    static int cnt = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer 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());
            }
        } // end input

        clean(R, C, D);
        System.out.println(cnt);
    }

    public static void clean(int r, int c, int d) {
        while (true) {
            boolean flag = false;
            if (map[r][c] == 0) { // 1. 청소
                map[r][c] = 2;
                cnt++;
            }

            for (int i = 0; i < 4; i++) {
                d = (d + (-1 + 4)) % 4; // 왼쪽 방향으로 회전
                int nr = r + dr[d];
                int nc = c + dc[d];
                if (nr >= 0 && nr < N && nc >= 0 && nc < M && map[nr][nc] == 0) {
                    flag = true;
                    r = nr;
                    c = nc;
                    break;
                }
            } // 2. 왼쪽으로 회전하며 4방향 보다가 청소되지 않은 칸 있으면 그 방향으로 회전 후 전진

            if (flag) continue; // 처음으로
            else { // 후진 체크
                int tmp = (d + 2) % 4;
                int nr = r + dr[tmp];
                int nc = c + dc[tmp];
                if (nr >= 0 && nr < N && nc >= 0 && nc < M) {
                    if (map[nr][nc] == 1) return; // 벽이라면 끝!
                    else { // 청소했던 칸이라면 후진!
                        r = nr;
                        c = nc;
                    }
                }
            }
        }
    }
}