[백준] 14503 로봇 청소기 - Java

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

 

문제 개요

로봇 청소기가 주어진 방에서 청소를 시작하며 특정 규칙에 따라 움직입니다. 방의 크기, 로봇 청소기의 초기 위치와 방향, 방의 상태(벽과 빈 칸)가 주어졌을 때, 로봇 청소기가 작동을 멈출 때까지 청소한 칸의 개수를 계산하는 문제입니다.

로봇 청소기의 동작 규칙:

1. 현재 칸 청소: 현재 위치가 청소되지 않은 빈 칸이면 청소.
2. 주변 확인:
   • 청소되지 않은 빈 칸이 있으면 반시계 방향으로 90도 회전.
   • 회전 후, 앞 칸이 청소되지 않은 빈 칸이면 전진.
3. 후진:
   • 주변에 청소되지 않은 칸이 없으면, 후진이 가능한 경우 후진.
   • 후진이 불가능하면 멈춤.

 

접근 방법

1. 입력 처리 및 초기화:
   • 방의 크기와 상태, 로봇의 초기 위치와 방향을 입력받습니다.
   • 방의 상태를 저장하는 2차원 배열 map과, 청소 여부를 확인하는 v 배열(visited 역할)을 초기화합니다.
   • map은 0(청소되지 않은 빈 칸), 1(벽)으로 구성되며, v는 방문한 칸을 표시합니다.
2. 로봇 청소기의 움직임 처리:
   • move 함수에서 로봇 청소기의 동작을 구현합니다.
   • 현재 위치를 청소하고, 규칙에 따라 움직입니다:
     • 청소 여부 확인: 현재 칸이 청소되지 않았으면 청소 후, 방문 배열에 표시합니다.
     • 주변 탐색: 네 방향을 확인하여 청소되지 않은 칸이 있으면 회전 후 전진.
     • 후진 처리: 네 방향 모두 청소가 완료되었거나 벽인 경우, 바라보는 방향을 유지한 채 후진 시도.
     • 종료 조건: 후진이 불가능하면 종료.
3. 방향과 이동 처리:
   • 방향은 0(북), 1(동), 2(남), 3(서)로 표시됩니다.
   • 방향 전환 및 이동은 방향 배열 dr(행 이동), dc(열 이동)을 사용하여 계산합니다:
     • 반시계 회전: (dir + 3) % 4
     • 후진: (dir + 2) % 4
4. 주변 칸 탐색 함수:
   • isClean 함수는 현재 칸 주변 4칸 중 청소되지 않은 빈 칸이 있는지 확인하여 이동 가능 여부를 반환합니다.

 

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

public class Main {
    static int[][] map;
    static boolean[][] v;
    static Pos pos;
    static int cleaned = 0;

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

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

    public static void move() {
        while (true) {
            int r = pos.r;
            int c = pos.c;
            int dir = pos.dir;

            // 1. 현재 칸 청소
            if (map[r][c] == 0 && !v[r][c]) {
                cleaned++;
                v[r][c] = true;
            }

            // 2. 주변에 청소되지 않은 칸 확인
            if (isClean(r, c)) {
                // 반시계 방향으로 회전
                dir = (dir + 3) % 4;
                if (r + dr[dir] >= 0 && c + dc[dir] >= 0 && r + dr[dir] < map.length && c + dc[dir] < map[0].length &&
                        map[r + dr[dir]][c + dc[dir]] == 0 && !v[r + dr[dir]][c + dc[dir]]) {
                    // 전진
                    r += dr[dir];
                    c += dc[dir];
                }
            } else {
                // 후진
                int nDir = (dir + 2) % 4;
                if (r + dr[nDir] < 0 || c + dc[nDir] < 0 || r + dr[nDir] >= map.length || c + dc[nDir] >= map[0].length ||
                        map[r + dr[nDir]][c + dc[nDir]] == 1) {
                    break;
                }
                r += dr[nDir];
                c += dc[nDir];
            }

            pos = new Pos(r, c, dir);
        }
    }

    public static boolean isClean(int r, int c) {
        for (int i = 0; i < 4; i++) {
            int nr = r + dr[i];
            int nc = c + dc[i];
            if (nr >= 0 && nc >= 0 && nr < map.length && nc < map[0].length &&
                    map[nr][nc] == 0 && !v[nr][nc]) {
                return true;
            }
        }
        return false;
    }

    public static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

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

        map = new int[N][M];
        v = new boolean[N][M];

        st = new StringTokenizer(br.readLine());
        pos = new Pos(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));

        for (int i = 0; i < map.length; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < map[i].length; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
    }

    static class Pos {
        int r, c, dir;

        public Pos(int r, int c, int dir) {
            this.r = r;
            this.c = c;
            this.dir = dir;
        }
    }
}