[백준 Java] 14503 로봇 청소기

문제 링크

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

 

풀이

청소기가 더 이상 움직일 수 없는 조건은 주변 칸이 전부 청소된 상태이고, 후진할 수 없는 경우이다.

while문을 실행하여 더 이상 움직일 수 없는 경우에 대해서 -1 값으로 처리했다.

move 함수는 로봇 청소기가 r, c, d값에 따라 한번 움직이는 함수이다. return값는 각 상황에 따른 새롭게 이동해야 하는 위치와 좌표가 반환된다.

move 함수에서 문제의 조건대로 함수를 실행한다.

 

개선할 점은 청소할 영역이 한가지만 남았는데, 로봇청소기가 해당 방향을 발견할때까지 뱅뱅 도는 경우이다

1 0 1 1 * 1 1 1 1

로봇 청소기가 *에 있을 때 0인 곳으로만 이동할 수 있는데 저 방향을 발견할때까지 계속 도는 경우가 있다.

어차피 청소하는 칸의 개수만 구하는 것이기 때문에 move 함수를 계속 실행시키는 것이 아니라 한 방향으로만 가야한다면 해당 방향을 바로 갈 수 있도록 return 값을 수정하는 것이 더 효율적인 코드라고 생각된다.

 

코드

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

public class Main_14503_로봇청소기 {

    static int N, M, res, map[][];
    static int[][] dir = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; //북 동 남 서

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokens = new StringTokenizer(br.readLine());

        N = Integer.parseInt(tokens.nextToken());
        M = Integer.parseInt(tokens.nextToken());
        map = new int[N][M];

        tokens = new StringTokenizer(br.readLine());
        //처음 위치와 방향
        int r = Integer.parseInt(tokens.nextToken());
        int c = Integer.parseInt(tokens.nextToken());
        int d = Integer.parseInt(tokens.nextToken());

        for (int i = 0; i < N; i++) {
            tokens = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                //0 청소되지 않은 칸, 1 벽
                map[i][j] = Integer.parseInt(tokens.nextToken());
            }
        }

        res = 0;

        while (r != -1 && c != -1 && d != -1) {
            int[] temp = move(r, c, d);
            r = temp[0];
            c = temp[1];
            d = temp[2];
        }

        System.out.println(res);
    }

    private static int[] move(int r, int c, int d) {
        //현재 칸 확인
        if (checkNowArea(r, c)) {
            //청소되지 않았다면 청소
            res++;
            map[r][c] = -1; //청소되었다고 표시
        }

        //주변 4칸 확인
        if (checkAroundArea(r, c)) {//다 청소된 경우
            //후진 가능한지 확인
            int[] temp = isBack(r, c, d);

            //후진 가능하다면 후진, 후진 불가능이면 작동 멈춤
            if (r == temp[0] && c == temp[1] && d == temp[2]) {
                //후진 불가능한 경우 멈춤
                return new int[]{-1, -1, -1};
            }
            //후진 가능한 경우
            return new int[]{temp[0], temp[1], temp[2]};

        } else {//청소되지 않은 칸이 있는 경우
            //방향 반시계로 90도 회전 -> 3 더하고 모듈러
            d = (d + 3) % 4;

            //앞쪽 칸이 청소되지 않은 빈칸이면 전진하고 다시 움직임
            int nx = r + dir[d][0];
            int ny = c + dir[d][1];
            if (isRange(nx, ny) && map[nx][ny] == 0) {//청소되지 않은 칸인 경우
                return new int[]{nx, ny, d}; //한칸 전진
            }
            //그냥 방향만 바꾸고 제자리
            return new int[]{r, c, d};

        }
    }

    private static int[] isBack(int r, int c, int d) {
        //현재 위치에서 후진 할 수 있는지 확인
        //현재 방향의 반대 방향 선택. 2를 더하고 모듈러
        int nd = (d + 2) % 4;
        int nx = r + dir[nd][0];
        int ny = c + dir[nd][1];

        //뒤로 갈 수 있고, 벽이 아닌 경우
        if (isRange(nx, ny) && map[nx][ny] != 1) return new int[]{nx, ny, d};
        return new int[]{r, c, d};

    }

    private static boolean checkAroundArea(int r, int c) {
        //주변에 0이 없다면 true
        for (int d = 0; d < 4; d++) {
            int nx = r + dir[d][0];
            int ny = c + dir[d][1];

            if (isRange(nx, ny) && map[nx][ny] == 0)
                return false;
        }
        return true;
    }

    private static boolean isRange(int x, int y) {
        if (x < 0 || y < 0 || x >= N || y >= M) return false;
        return true;
    }

    private static boolean checkNowArea(int r, int c) {
        if (map[r][c] == 0) return true; //청소되지 않은 칸이라면 true
        return false;
    }
}