[ 백준 14503번 ] 로봇 청소기

1. 문제

14503번: 로봇 청소기

 

 

2. 풀이

단순한 구현 문제이지만, 로봇의 동작이 다소 복잡하게 정의되어 있어 난이도가 올라간 것으로 보인다. 하지만 문제에서 정의한 청소기의 동작 방식을 순차적으로 잘 구현만 한다면, 큰 어려움은 없다.

 

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

 

필자의 경우 시작 위치와 방향을 갖고 있는 Robot 객체를 생성해, Robot이 스스로 동작하고 움직이도록 처리하였다.

 

3. 소스코드

public class sml_14503_robotVacuum {
    static final int[] dy = {-1, 0, 1, 0};
    static final int[] dx = {0, 1, 0, -1};

    static int N, M;
    static int[][] map;
    static boolean[][] cleaned;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        Robot robot = new Robot(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));

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

        robot.activate();

        bw.write(robot.getCleanedCnt() + "");
        bw.close();
        br.close();
    }

    static boolean isOutOfRange(int y, int x) {
        return y < 0 || x < 0 || N <= y || M <= x || map[y][x] == 1;
    }

    static class Robot {
        int y, x, dir;
        int cleanedCnt = 0;

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

        public int getCleanedCnt() {
            return cleanedCnt;
        }

        // 청소기 동작시키기
        void activate() {
            while (true) {
                // 1번 동작 - 청소되지 않은 경우, 현재 칸을 청소한다.
                if (!cleaned[y][x] && map[y][x] == 0) {
                    cleanedCnt++;
                    cleaned[y][x] = true;
                }

                int ny = y;
                int nx = x;
                
                // 3번 동작 - 주변 4칸 중 청소되지 않은 빈 칸이 있는 경우
                if (checkNotCleanedAreaExist(y, x)) {
                    // 방향 전환
                    rotate();

                    ny += dy[dir];
                    nx += dx[dir];
                    
                    // 청소되지 않은 빈칸이 아니라면 패스
                    if (isOutOfRange(ny, nx) || cleaned[ny][nx]) continue;
                } else {
                    // 반대 방향으로 진행하기 위한 임시 방향
                    int tempDir = (dir + 2) % 4;

                    ny += dy[tempDir];
                    nx += dx[tempDir];
                    
                    // 후진할 수 없다면 동작을 멈춤
                    if (isOutOfRange(ny, nx)) break;
                }
                y = ny;
                x = nx;
            }
        }

        // 4방향에 청소되지 않은 칸이 있는지 확인
        boolean checkNotCleanedAreaExist(int y, int x) {
            for (int d = 0; d < 4; d++) {
                int ny = y + dy[d];
                int nx = x + dx[d];
                if (!isOutOfRange(ny, nx) && !cleaned[ny][nx]) {
                    return true;
                }
            }
            return false;
        }
        
        // 반시계방향으로 90도 회전
        void rotate() {
            this.dir = (this.dir + 3) % 4;
        }
    }
}

 

GitHub - kwanik-kor/BOJ: Baekjoon Online Judge - explanation of solved problems and complete code