SW 역량 테스트 기출 문제(로봇 청소기)

[로봇 청소기 _ 14503]

 

 

* 조건

1. 로봇의 현재 위치와 로봇 기준에서 나아가는 방향(북,동,남,서)을 입력받는다.
2. 현재 위치에서 청소가 가능하면 청소를 한다
3. 이후 방향을 탐색하고 4곳 모두 청소할 곳이 없다면 후진을 하고, 후진을 할 때 벽에 부딪히면 종료
4. 한 번 청소한 방을 다시 청소하면 안된다 (후진 시 이동은 가능)

* 알고리즘

- 주어진 명령에 맞게 작업을 진행: 시뮬레이션

 

* 로직(Logic)

- 우리가 바라보는 맵 기준의 방향과 객체(로봇)이 바라보는 방향의 인덱스 관계를 고려해야 한다

- 로봇 기준에서 북쪽(0)일때 맵에서는 서(3), 남(2), 동(1), 북(0) 식으로 회전을 하게되고, 나머지 방향도 이와같은 고정 규칙이 존재하게 된다.  

 

- 현재 위치에서 청소가 가능하면 count++ 하고, 로봇이 바라보는 방향을 기준의 왼쪽 방향부터 주변 칸을 탐색한다

- 탐색 중 이동이 가능하면 로봇의 방향을 바꿔주고 해당 좌표로 이동

- 이동이 불가능하다면 로봇이 향하고 있는 방향의 반대 방향으로 후진을 시키고, 후진할 곳이 벽('1')이라면 종료

 

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

class Position_14503 {
    public int y,x;
    public int dir; //현재 로봇이 바라보는 방향

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

public class Problem_14503 {

    static int n, m;
    static int[][] map;

    //북 동 남 서
    static int[] dy = {-1, 0, 1, 0};
    static int[] dx = {0, 1, 0, -1};

    static int[][] directions = {
            //현재 방향이 북쪽이면: 서 남 동 북
            {3, 2, 1, 0},
            //현재 방향이 동쪽이면: 북 서 남 동
            {0, 3, 2, 1},
            //현재 방향이 남쪽이면: 동 북 서 남
            {1, 0, 3, 2},
            //현재 방향이 서쪽이면: 남 동 북 서
            {2, 1, 0, 3},
    };

    static Queue<Position_14503> queue_robot = new LinkedList<>();
    static boolean[][] checked;

    static boolean mark = false;
    static int count = 0;

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

        String config = br.readLine();
        st = new StringTokenizer(config, " ");
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        map = new int[n][m];
        checked = new boolean[n][m];

        config = br.readLine();
        st = new StringTokenizer(config, " ");
        int y = Integer.parseInt(st.nextToken());
        int x = Integer.parseInt(st.nextToken());

        Position_14503 robot = new Position_14503(y, x);
        robot.dir = Integer.parseInt(st.nextToken());
        queue_robot.offer(robot);

        for(int i=0; i<n; ++i){
            String input = br.readLine();
            st = new StringTokenizer(input, " ");
            for(int j=0; j<m; ++j){
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        doProcess();
        System.out.println(count);

    }

    private static void doProcess() {
        //현재 위치를 청소 -> 방향 기준 왼쪽으로 순차적으로 탐색 -> 청소 가능하면 로봇.dir을 변경 -> 이동
        //청소할 곳이 없다면 왼쪽 방향으로 회전 (로봇.dir을 덮지 않음)
        //인접한 4군데 모두 청소할 필요가 없으면 -> 현재 로봇이 가리키는 방향(로봇.dir)을 유지한채 이전 로봇의 위치로 이동
        //모두 청소가 되어있고 뒤로 후진 시 벽이라면 종료

        while (!mark){
            Position_14503 q = queue_robot.poll();

            //현재 위치를 청소할 수 있으면 -> 청소 -> count++ -> 4방향 탐색 -> 이동
            if(map[q.y][q.x] == 0 && !checked[q.y][q.x]) {
                checked[q.y][q.x] = true;
                count++;

                //4방향 탐색 후, 4방향 모두 청소가 끝났거나 벽에 부딪힌 경우 처리 (후진 or 종료)
                if(!searchRoom(q)){
                    doException(q);
                }
            }

            //해당 위치가 이미 청소 되어있다면
            else if(map[q.y][q.x] == 0 && checked[q.y][q.x]){
                //4방향 탐색 후, 4방향 모두 청소가 끝났거나 벽에 부딪힌 경우 처리 (후진 or 종료)
                if(!searchRoom(q)){
                    doException(q);
                }
            }
        }
    }

    private static boolean searchRoom(Position_14503 currentRobot) {
        //현재 로봇이 가리키는 방향 기점으로 왼쪽부터 탐색
        int dir = currentRobot.dir;
        Position_14503 moveRobot;

        for(int i=0; i<4; ++i){
            int index = directions[dir][i];

            int moveY = currentRobot.y + dy[index];
            int moveX = currentRobot.x + dx[index];

            //청소 가능하면 방향 변경 후 로봇 이동
            if(map[moveY][moveX] == 0 && !checked[moveY][moveX]){
                moveRobot = new Position_14503(moveY, moveX);
                moveRobot.dir = index;
                queue_robot.offer(moveRobot);

                return true;
            }
        }

        return false;
    }

    private static void doException(Position_14503 currentRobot) {
        int dir = currentRobot.dir;
        Position_14503 moveRobot;

        int backY = currentRobot.y - dy[dir];
        int backX = currentRobot.x - dx[dir];

        //후진했을 때 벽이 아니라면 방향 유지한채로 후진
        if(map[backY][backX] == 0){
            moveRobot = new Position_14503(backY, backX);
            moveRobot.dir = dir;
            queue_robot.offer(moveRobot);
            return;
        }
        //후진 후 벽이 존재하면 멈춤
        else if(map[backY][backX] == 1){
            mark = true;
        }
    }
}

 

 

우리가 바라보는 맵 기준의 방향과 문제에 주어진 객체(뱀, 로봇) 기준의 방향간의 규칙을 찾고 이를 활용해 인덱스로 관계를 맺는게 중요한 핵심이라는 것을 느꼈다.

이와 같은 유형의 시뮬레이션 문제가 나온다면, 먼저 이러한 접근법을 사용해보면 좋을 거 같다.