[JAVA] 백준 14503

 

 

 

 

14503번: 로봇 청소기

문제

로봇 청소기와 방의 상태가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오.

풀이

로봇 청소기가 동작하는 방식을 BFS 로직과 비슷하게 구현해보았습니다.

📌 입력

        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());

        A = new int[N][M];

        st = new StringTokenizer(br.readLine(), " ");
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        // 0 북쪽, 1 동쪽, 2 남쪽, 3 서쪽
        int d = Integer.parseInt(st.nextToken());

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

• 방의 크기 N, M
• 청소기의 현재 위치 및 방향 a, b, d
• 방의 상태 A[]

이 문제에서는 방의 가장 동, 서, 남, 북쪽은 벽으로 막혀있기 때문에 ArrayIndexOutOfBoundsException에 대해서 고민하지 않고 딱 맞게 배열을 만들었다.

📌 Coordinate, 청소기의 위치 및 방향

    static class Coordinate{
        int x;
        int y;
        int d;
        public Coordinate(int x, int y, int d){
            this.x = x;
            this.y = y;
            this.d = d;
        }

        public void rotateDirection(){
            this.d = (this.d + 3) % 4;
        }

        public int backDirection(){
            return (this.d +2) % 4;
        }
    }

청소기의 위치와 방향을 담는 클래스를 만들었다.

• roateDirection() 메서드는 현재 청소기의 방향을 반시계 방향으로 90도 회전하는 메서드이다.
• backDirection() 메서드는 현재 청소기의 방향을 바꾸지 않고 현재 방향의 반대 방향을 출력하는 메서드이다.

📌 방 청소

    public static void BFS(Coordinate start){
        if(A[start.x][start.y] == 1) return;
        Queue<Coordinate> q = new LinkedList<>();

        count++;
        A[start.x][start.y] = 2;
        q.add(start);
        while (!q.isEmpty()){
            Coordinate now = q.poll();
            int c = 0;
            for(int i=0; i<4; i++){
                int a = now.x + xValue[i];
                int b = now.y + yValue[i];
                if(A[a][b] == 0){
                    c++;
                    now.rotateDirection();
                    break;
                }
            }
            // 주변에 청소할 곳이 없는 경우
            if(c == 0){
                int back = A[now.x + xValue[now.backDirection()]][now.y + yValue[now.backDirection()]];
                // 뒤가 벽이 아니라면 (2 또는 0)
                if(back % 2 == 0){
                    // 뒤로 이동
                    q.add(new Coordinate(now.x + xValue[now.backDirection()],now.y+ yValue[now.backDirection()], now.d));
                    continue;
                    // 뒤가 벽이라면 (1)
                }else{
                    return;
                }
            }
            // 주변에 청소할 곳이 있는 경우 (청소기가 바라보는 방향 앞의 구역이 청소 가능한 구역인 경우)
            if(A[now.x + xValue[now.d]][now.y + yValue[now.d]] == 0){
                A[now.x + xValue[now.d]][now.y + yValue[now.d]] = 2;
                count++;
                q.add(new Coordinate(now.x + xValue[now.d], now.y + yValue[now.d], now.d));
                continue;
            }
            // 주변에 청소할 곳이 있지만 청소기가 바라보는 방향이 아닌 경우
            q.add(now);
        }

    }

코드는 문제에 나와있는 청소기의 동작에 따라서 작성했다.

1. 현재 칸이 아직 청소되지 않은 경우 청소해준다.
2. 만약 현재 칸의 주변 4칸 중에서 청소되지 않은 구역이 없다면 바라보는 방향 그대로 후진한다.
3. 만약 뒤쪽 칸이 벽으로 막혀있다면 청소를 종료한다.
4. 만약 현재 칸의 주변 4칸 중에서 청소되지 않은 구역이 있다면 반시계 방향으로 90도 회전한다.
5. 만약 현재 바라보는 방향의 앞의 칸이 청소되지 않은 구역이라면 한 칸 전진한다.
6. 반복

📌 전체 코드

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

class Main {
    static int[][] A;
    static int count = 0;
    // 0 북쪽, 1 동쪽, 2 남쪽, 3 서쪽
    static int[] xValue = {-1, 0, 1, 0};
    static int[] yValue = {0, 1, 0, -1};
    public static void main(String[] args) 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());

        A = new int[N][M];

        st = new StringTokenizer(br.readLine(), " ");
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        // 0 북쪽, 1 동쪽, 2 남쪽, 3 서쪽
        int d = Integer.parseInt(st.nextToken());

        for(int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine(), " ");
            for(int j=0; j<M; j++){
                A[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        BFS(new Coordinate(a, b, d));
        System.out.println(count);

    }

    public static void BFS(Coordinate start){
        if(A[start.x][start.y] == 1) return;
        Queue<Coordinate> q = new LinkedList<>();

        count++;
        A[start.x][start.y] = 2;
        q.add(start);
        while (!q.isEmpty()){
            Coordinate now = q.poll();
            int c = 0;
            for(int i=0; i<4; i++){
                int a = now.x + xValue[i];
                int b = now.y + yValue[i];
                if(A[a][b] == 0){
                    c++;
                    now.rotateDirection();
                    break;
                }
            }
            // 주변에 청소할 곳이 없는 경우
            if(c == 0){
                int back = A[now.x + xValue[now.backDirection()]][now.y + yValue[now.backDirection()]];
                // 뒤가 벽이 아니라면 (2 또는 0)
                if(back % 2 == 0){
                    // 뒤로 이동
                    q.add(new Coordinate(now.x + xValue[now.backDirection()],now.y+ yValue[now.backDirection()], now.d));
                    continue;
                    // 뒤가 벽이라면 (1)
                }else{
                    return;
                }
            }
            // 주변에 청소할 곳이 있는 경우 (청소기가 바라보는 방향 앞의 구역이 청소 가능한 구역인 경우)
            if(A[now.x + xValue[now.d]][now.y + yValue[now.d]] == 0){
                A[now.x + xValue[now.d]][now.y + yValue[now.d]] = 2;
                count++;
                q.add(new Coordinate(now.x + xValue[now.d], now.y + yValue[now.d], now.d));
                continue;
            }
            // 주변에 청소할 곳이 있지만 청소기가 바라보는 방향이 아닌 경우
            q.add(now);
        }

    }

    static class Coordinate{
        int x;
        int y;
        int d;
        public Coordinate(int x, int y, int d){
            this.x = x;
            this.y = y;
            this.d = d;
        }

        public void rotateDirection(){
            this.d = (this.d + 3) % 4;
        }

        public int backDirection(){
            return (this.d +2) % 4;
        }
    }
}

결과