[ 백준 14503 ] 로봇청소기 (java)

 

[ 백준 14503 ] 로봇청소기 (자바)

https://www.acmicpc.net/problem/14503

14503번: 로봇 청소기

 

 

핵심

1 시뮬레이션 (+메모이제이션) / bfs 문제 

시뮬이나 bfs 문제 특징은 조건을 얼마나 잘 이해했는지 중요

 

2 기존 방향에서 왼쪽 회전 또는 역방향 회전 ( 북:0, 동: 1, 남: 2, 서: 3) 

왼쪽방향 = ( 기존 방향 + 3 ) % 4

역방향 = ( 기존 방향 + 2 ) % 4 

 

3 나머지는 코드 주석 참고 

 

 

추가적으로 더 궁금한 점 있으면 댓글 달아주세요

 

코드

 
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
/*
 * 로봇 청소기 
 * 
 *  15/42 
 *  
 *  오류
 *  while(ndir != robot.dir)라고 해서 오류났다.
 *  원래 마지막에 정면을 확인해야하는데 정면을 확인안해서 값이 더 작게 나왔었음
 *   
 */
public class Main {
    static int N, M;
    static int[][] map;
    static boolean[][] clean; // 로봇 청소기가 이미 청소했는지 확인 
    // 동서남북 방향 
    static int[][] delta = {
            {-1, 0},
            {0, 1},
            {1, 0},
            {0, -1}
    };
    // 로봇 청소기 객체 
    static class cleaner{
        int y, x, dir;
        cleaner(int y, int x, int dir){
            this.y = y;
            this.x = x;
            this.dir = dir; 
        }
    }
    // 현재 위치가 범위 이내인가 
    static boolean isRange(int y, int x) {
        return y >= 0 && y < N && x >= 0 && x < M;
    }
    public static void main(String[] args)throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[N][M];
        clean = new boolean[N][M];
        
        st = new StringTokenizer(br.readLine());
        int iy, ix, idir;
        iy = Integer.parseInt(st.nextToken());
        ix = Integer.parseInt(st.nextToken());
        idir = Integer.parseInt(st.nextToken());
        cleaner robot = new cleaner(iy, ix, idir);
    
        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());
            }
        }
        
        // 현재 이동가능한가
        boolean possible = true;
        
        // ndir: 검사할 새 방향, back: 역방향
        int ndir, back, count = 1;
        
        // 시작 위치 청소하고 시작 
        clean[robot.y][robot.x] = true;
        
        // 청소 시작 
        while(true) {
            
            // 더 청소가 가능한가, false 초기화 
            possible = false;
            
            // 4방향확인 
            ndir = (robot.dir + 3)%4;
            int ny, nx;
            for(int c = 0 ; c < 4; c++) {
                // ndir(새 방향)에 청소할 꺼리가 존재? 
                ny = robot.y + delta[ndir][0];
                nx = robot.x + delta[ndir][1];
                // 범위 이내, 청소 안함. 벽도 아님 
                if(isRange(ny, nx) && !clean[ny][nx] && map[ny][nx] != 1) {
                    // 청소할꺼리 찾음, 회전 후 1칸 이동 
                    robot.dir = ndir;
                    robot.y = ny;
                    robot.x = nx;
                    clean[robot.y][robot.x] = true;
                    count++;
                    possible = true;
                    break;
                }
                ndir = (ndir + 3)%4;
            }
 
            // 청소불가 
            if(!possible) {
                back = (robot.dir+2)%4;
                ny = robot.y + delta[back][0];
                nx = robot.x + delta[back][1];
                // 후진 가능? 범위 이내고 벽이 아니다
                if(isRange(ny, nx) && map[ny][nx] != 1) {
                    robot.y = ny;
                    robot.x = nx;
                }else {
                // 후진도 불가 -> 종료 
                    break;
                }
            }
            
        }
        System.out.println(count);
    }
 
}