BOJ) 로봇 청소기

로봇 청소기

14503번: 로봇 청소기

풀이

 

푸는데 많은 시간을 소요했다.

1. 현재 위치를 청소한다.
2. 현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다.
   1. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.
   2. 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.
   3. 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.
   4. 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.

로봇 청소기는 이미 청소되어있는 칸을 또 청소하지 않으며, 벽을 통과할 수 없다.

위의 사항이 문제의 조건이다....

정말 많다..

먼저, 해석하는데 시간이 오래걸렸다.

 

먼저, 로봇 청소기의 위치에서 현재 좌표를 청소한다. 이 때, 청소가 되어있는 곳이면 청소하지 않는다.

로봇청소기가 보고있는 방향을 기준으로, 왼쪽 방향을 검사한다.

왼쪽칸에 청소하지 않은 공간이 있으면, 그 방향으로 회전해서 해당 칸으로 옮기고 청소한다.

만약 청소한 공간이라면, 그 방향으로 회전만 한다.

 

청소한 공간이 없어서 4번 회전한 경우에, 바라보는 방향을 유지한 채로 한칸 후진을 한다.

하지만, 후진하는 곳이 벽이라면 작동을 멈춘다.

 

위와 같이 해석하는게, 문제푸는데 조금 더 수월한 것 같다.

맵에서 청소한 칸은 2로 바꿔주면서 답을 찾아나갔다.

그리고 각 방향마다 탐색해야 하는 곳으로 증감해줄 dx, dy를 만들어줘서 조금 더 수월하게 풀었다.

0번은 북쪽을 뜻하는데, 탐색해야하는 방향은 서쪽이므로, dx[0] = -1, dy[0] = 0 을 초기화해줬다.

나머지 방향도 해당 방향의 서쪽편의 좌표로 갈 수 있는 증감을 저장했다.

 

나머지 코드는 막 어렵다고 할 수는 없지만, 시뮬레이션의 특성상 코드가 길어지면서 머리가 복잡해졌다.

rotate를 하는 부분, 그리고 로봇 청소기의 방향을 저장해주는 부분에서 시간이 조금 걸렸다.

 

 

코드

 

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

public class Main {
    final static int DIRECTIONS =4, EMPTY =0, WALL =1, CLEAN=2;
    final static int[] dx = {-1,0,1,0}, dy = {0,-1,0,1};
    static int r,c;
    static int[][] map;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        r = getIntValue(st);
        c = getIntValue(st);
        map = new int[r][c];

        st = new StringTokenizer(br.readLine());
        int tmpY = getIntValue(st);
        Pos robot = new Pos(getIntValue(st), tmpY, getIntValue(st));

        for(int y=0; y<r; y++) {
            st = new StringTokenizer(br.readLine());
            for(int x=0; x<c; x++) {
                map[y][x] = getIntValue(st);
            }
        }
        br.close();
        solution(robot);
    }

    private static void solution(Pos robot) {
        LinkedList<Pos> moveList = new LinkedList<>();
        moveList.offer(robot);
        int answer =0;
        int rotate =0;

        while(!moveList.isEmpty()) {
            Pos pos = moveList.poll();
            int x = pos.x;
            int y = pos.y;
            int dir = pos.dir;
            int nextX, nextY, nextDir;

            if (map[y][x] == EMPTY) {
                answer++;
                map[y][x] = CLEAN;
            }

            if(rotate == DIRECTIONS) {
                int calDir = getNewDir(dir);
                nextX = x + dx[calDir];
                nextY = y + dy[calDir];
                if(map[nextY][nextX] == WALL) { break; }

                moveList.offer(new Pos(nextX,nextY,dir));
                rotate =0;
            } else {
                nextDir = getNewDir(dir);
                nextX = x + dx[dir];
                nextY = y + dy[dir];
                if(map[nextY][nextX] == EMPTY) {
                    moveList.offer(new Pos(nextX,nextY,nextDir));
                    rotate =0;
                }
                else {
                    moveList.offer(new Pos(x,y,nextDir));
                    rotate++;
                }
            }
        }
        System.out.println(answer);
    }

    private static int getIntValue(StringTokenizer st) { return Integer.parseInt(st.nextToken()); }

    private static int getNewDir(int dir) {
        int result = (dir+3)%DIRECTIONS;
        return result;
    }

    private static class Pos {
        int x,y,dir;

        public Pos (int x, int y, int dir) {
            this.x =x;
            this.y =y;
            this.dir =dir;
        }
    }
}