[백준 14530, Java] 로봇청소기

새 버전(2021.02.25)

alwaysbemoon.tistory.com/233

[백준 14503, Java] 로봇청소기

 

---

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws  Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        int N;
        int M;
        int[][] map;
        Robot robot;
        int x, y, direction;

        st = new StringTokenizer(br.readLine()," ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[N][M];

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

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

        RobotCleaner robotCleaner = new RobotCleaner(robot, N, M, map);
        robotCleaner.cleanMap(robot);
        bw.write(String.valueOf(robotCleaner.cleanCount));
        bw.flush();


    }
}
class Robot{
    int x;
    int y;
    int direction;

    final int[] directionX = {-1,0,1,0};
    final int[] directionY = {0,1,0,-1};

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

    public Robot turnLeft(Robot currentRobot,int count){
        int leftDirection = (currentRobot.direction+3*count)%4;
        int leftX = currentRobot.x + directionX[leftDirection];
        int leftY = currentRobot.y + directionY[leftDirection];

        return new Robot(leftX, leftY, leftDirection);
    }

    public Robot goBack(Robot currentRobot){
        int backX = currentRobot.x + directionX[(currentRobot.direction+2)%4];
        int backY = currentRobot.y + directionY[(currentRobot.direction+2)%4];

        return new Robot(backX, backY, currentRobot.direction);
    }

    public String toString(){
        return "("+x+","+y+")"+"direction:"+direction;
    }
}
class RobotCleaner{
    Robot robot;

    int N;
    int M;
    int[][] map;
    final int BLANK =0;
    final int WALL =1;
    final int CLEANED =2;

    int cleanCount;

    RobotCleaner(Robot robot, int N ,int M, int[][] map){
        this.robot =robot;
        this.N = N;
        this.M = M;
        this.map = map;
        cleanCount =0;
    }

    public void cleanMap(Robot robot){
       //현재위치가 청소가 안되어 있으면 청소한다.
        if(map[robot.x][robot.y] ==BLANK){
            map[robot.x][robot.y]=CLEANED;
            ++cleanCount;
        }

        //현재위치 기준 왼쪽 방향으로 탐색
        Queue<Robot> candidateRobotClean = new LinkedList<>();
        for(int count =1; count <=4 ;count++){
            Robot leftRobot = robot.turnLeft(robot, count);

            if(leftRobot.x>=0 && leftRobot.x<N && leftRobot.y>=0 && leftRobot.y<M){
                candidateRobotClean.add(robot.turnLeft(robot, count));
            }
        }
        //왼쪽방향에 청소할 곳이 있는지 확인
        while(!candidateRobotClean.isEmpty()){
            Robot leftRobot = candidateRobotClean.remove();
            if(map[leftRobot.x][leftRobot.y]==BLANK){
                cleanMap(leftRobot);
                return;
            }
        }

        //청소할 수 있는 곳이 없으면 뒤로 후진할 수 있는지 확인
        Robot backRobot = robot.goBack(robot);
        if(backRobot.x <0 || backRobot.x >=N || backRobot.y<0 || backRobot.y>=M){
            return;
        }
        else if(map[backRobot.x][backRobot.y]==WALL){
            return;
        }
        else{
            cleanMap(backRobot);
        }





    }
}

 

 

 

반례

 

6 6
1 1 0 
1 1 1 1 1 1
1 0 0 1 0 1
1 1 0 0 0 1
1 1 0 1 1 1
1 0 0 0 0 1
1 1 1 1 1 1

 

답: 6