BOJ 14503 - 로봇 청소기

14503번: 로봇 청소기 (acmicpc.net)

 

로봇 청소기의 이동 = 바라보는 방향이 존재

처음 빈칸은 전부 청소되지 않은 상태

1. 현재 칸이 청소되지 않은 경우 현재 칸을 청소
2. 현재 칸의 주변 4칸 중 청소되지 않은 빈칸이 없는 경우
   1. 바라보는 방향을 유지한 채로 한 칸 후진할 수 있다면 한 칸 후진하고 1번으로
   2. 바라보는 방향의 뒤쪽 칸이 벽이라 후진할 수 없다면 작동을 멈춘다.
3. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 있는 경우
   1. 반시계 방향으로 90도 회전한다.
   2. 바라보는 방향을 기준으로 앞쪽이 청소되지 않은 빈칸인 경우 한 칸 전진한다.
   3. 1번으로 돌아간다.

 

필요한 기능을 정리해보자.

1. 현재 위치의 청소 여부 판단
2. 주변 4칸의 청소 여부 판단
3. 후진
4. 전진
5. 반시계 90도 회전

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

public class Main {

    static FastReader scan = new FastReader();
    static int[][] DIRECTION = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}}; // 북서남동
    static int N, M;
    static Robot robot;
    static int[][] map;

    static class Robot {
        int r;
        int c;
        int d;

        public Robot(int r, int c, int d) {
            this.r = r;
            this.c = c;
            this.d = d;
        }

        void moveForward() {
            r += DIRECTION[d][0];
            c += DIRECTION[d][1];
        }

        void moveBack() {
            r -= DIRECTION[d][0];
            c -= DIRECTION[d][1];
        }

        void rotate() {
            d = (d + 1) % 4;
        }
    }

    static class Room {
        int[][] map;
        Robot robot;
        int cleanCount;

        public Room(int[][] map, Robot robot) {
            this.map = map;
            this.robot = robot;
        }

        public void clean() {
            while (true) {
                if (map[robot.r][robot.c] == 0) {
                    map[robot.r][robot.c] = 2;
                    cleanCount++;
                }

                // 주변 4칸을 탐색
                if (existUncleanRoom(map, robot.r, robot.c)) {
                    // 4칸 중 청소되지 않은 빈 칸이 존재한다.
                    for (int i = 0; i < 4; i++) {
                        robot.rotate();
                        int nr = robot.r + DIRECTION[robot.d][0];
                        int nc = robot.c + DIRECTION[robot.d][1];
                        if (nr < 0 || nr >= N || nc < 0 || nc >= M) {
                            continue;
                        }
                        if (map[nr][nc] == 0) {
                            robot.moveForward();
                            break;
                        }
                    }

                } else {
                    // 4방향 다 봤는데 청소되지 않은 칸이 없다.
                    robot.moveBack();
                    if (map[robot.r][robot.c] == 1) {
                        // 후진했는데 벽인 경우 종료
                        return;
                    }
                }
            }
        }

        private boolean existUncleanRoom(int[][] map, int r, int c) {
            for (int d = 0; d < 4; d++) {
                if (map[r + DIRECTION[d][0]][c + DIRECTION[d][1]] == 0) {
                    return true;
                }
            }
            return false;
        }

        public int getCleanCount() {
            return cleanCount;
        }
    }

    static void input() {
        N = scan.nextInt();
        M = scan.nextInt();
        map = new int[N][M];

        // 로복 좌표, 방향
        int r = scan.nextInt();
        int c = scan.nextInt();
        int d = scan.nextInt();
        if (d == 0) {
            // 북
            d = 0;
        } else if (d == 1) {
            // 동
            d = 3;
        } else if (d == 2) {
            // 남
            d = 2;
        } else {
            //서
            d = 1;
        }

        robot = new Robot(r, c, d);
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                map[i][j] = scan.nextInt(); // 0 빈칸 1 벽
            }
        }
    }

    public static void main(String[] args) {
        input();
        Room room = new Room(map, robot);
        room.clean();
        System.out.println(room.getCleanCount());
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}