BOJ14503 로봇청소기

<Solution>

1. 현재 위치 청소 -> visited = true

2. 현재 위치에서 바로 왼쪽 청소가능? - 방향 바꾸기 , 한 칸 전진 후 다시 (1)번 진행

3. 현재 위치에서 바로 왼쪽 청소불가능? - 방향만 바꾸기 후 다시 (2)번 진행

4. 4 방향 모두 확인 했을 때 청소 불가능? - 그 때의 방향에서 한 칸 후진 후 다시 (2)번 진행

5. 후진도 불가능? - 종료

6. visited에 있는 true의 개수가 로봇 청소기가 청소한 공간임

first() : 현재 위치를 청소하는 함수

second() : (1) 현재방향과 현재위치에서 4 방향 모두 청소가 가능한지 검사

  (2) 현재방향과 현재위치를 기준으로 바로 왼쪽이 청소가 가능하면 방향과 위치 갱신 다시 first()로

  (3) 바로 왼쪽이 청소가 불가능하면 방향만 바꾸고 다시 second()로

third() : (1) 현재방향과 현재위치에서 후진가능한지 확인

     (2) 가능하면 후진 후 다시 second()로

     (3) 불가능하면 모든 함수 끝낼 수 있게 flag변경해주고 종료

 

<Source Code>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
 
    private static int[][] map;
    private static boolean[][] visited;
    private static int N;
    private static int M;
    private static int robot_r;
    private static int robot_c;
    private static int robot_dir;
    private static boolean world_flag;
    private static boolean[] dir_check;
 
    public static void main(String[] args) throws Exception {
 
        // input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine().trim(), " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[N][M];
        visited = new boolean[N][M];
        dir_check = new boolean[4]; // 이동했을 때만 초기화
        st = new StringTokenizer(br.readLine().trim(), " ");
        robot_r = Integer.parseInt(st.nextToken());
        robot_c = Integer.parseInt(st.nextToken());
        robot_dir = Integer.parseInt(st.nextToken());
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine().trim(), " ");
            for (int j = 0; j < M; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
 
        // start
        world_flag = false;
        while (!world_flag) {
            // 1. 현재 위치 청소
            first();
        }
        int cnt = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if(visited[i][j])
                    cnt++;
            }
        }
        System.out.println(cnt);
    }
 
    private static void first() {
        // visited 체크만
        dir_check = new boolean[4];
        visited[robot_r][robot_c] = true;
        second();
        if(world_flag)
            return;
    }
 
    private static int[] dr = {-1,0,1,0};
    private static int[] dc = {0,1,0,-1};
    
    private static void second() {
        // 현재방향과 현재위치에서 네 방향이 모두 청소 불가능한 곳이면 third로
        boolean flag = false;
        for (int i = 0; i < 4; i++) {
            int nr = robot_r + dr[i];
            int nc = robot_c + dc[i];
            if(nr>=0 && nr<N && nc>=0 && nc<M) {
                if(map[nr][nc] == 0 && !visited[nr][nc])
                    flag = true;
            }
        }
        if(!flag) {
            third();
            if(world_flag)
                return;
        }
        // 로봇의 현재 위치와 방향을 기준으로 왼쪽 청소가능한지 체크
        if (robot_dir == 0) {
            int robot_nr = robot_r;
            int robot_nc = robot_c - 1;
            // 현재방향과 위치를 기준으로 왼쪽이 청소 가능한 곳이다
            if(robot_nc >= 0 && map[robot_nr][robot_nc] == 0 && !visited[robot_nr][robot_nc]) {
                robot_r = robot_nr;
                robot_c = robot_nc;
                robot_dir = 3;
                first();
            }
            // 현재방향과 위치를 기준으로 왼쪽이 청소 불가능한 곳이다
            else if(robot_nc >= 0 && (map[robot_nr][robot_nc] == 1 || visited[robot_nr][robot_nc])){
                robot_dir = 3;
                second();
            }
        } else if (robot_dir == 1) {
            int robot_nr = robot_r - 1;
            int robot_nc = robot_c;
            if(robot_nr >= 0 && map[robot_nr][robot_nc] == 0 && !visited[robot_nr][robot_nc]) {
                robot_r = robot_nr;
                robot_c = robot_nc;
                robot_dir = 0;
                first();
            }
            else {
                robot_dir = 0;
                second();
            }
        } else if (robot_dir == 2) {
            int robot_nr = robot_r;
            int robot_nc = robot_c + 1;
            if(robot_nc < M && map[robot_nr][robot_nc] == 0 && !visited[robot_nr][robot_nc]) {
                robot_r = robot_nr;
                robot_c = robot_nc;
                robot_dir = 1;
                first();
            }
            else {
                robot_dir = 1;
                second();
            }
        } else if (robot_dir == 3) {
            int robot_nr = robot_r + 1;
            int robot_nc = robot_c ;
            if(robot_nr < N && map[robot_nr][robot_nc] == 0 && !visited[robot_nr][robot_nc]) {
                robot_r = robot_nr;
                robot_c = robot_nc;
                robot_dir = 2;
                first();
            }
            else {
                robot_dir = 2;
                second();
            }
        }
    }
 
    private static void third() {
        // 현재방향에서 후진
        if(robot_dir == 0) {
            int robot_nr = robot_r + 1;
            // 후진가능
            if(robot_nr < N && map[robot_nr][robot_c] == 0) {
                robot_r = robot_nr;
                second();
            }
            else if(map[robot_nr][robot_c] == 1){
                world_flag = true;
                return;
            }
        } else if(robot_dir == 1) {
            int robot_nc = robot_c - 1;
            if(robot_nc >= 0 && map[robot_r][robot_nc] == 0) {
                robot_c = robot_nc;
                second();
            }
            else if(map[robot_r][robot_nc] == 1){
                world_flag = true;
                return;
            }
        } else if(robot_dir == 2) {
            int robot_nr = robot_r - 1;
            // 후진가능
            if(robot_nr >= 0 && map[robot_nr][robot_c] == 0) {
                robot_r = robot_nr;
                second();
            }
            else if(map[robot_nr][robot_c] == 1){
                world_flag = true;
                return;
            }
        } else if(robot_dir == 3) {
            int robot_nc = robot_c + 1;
            if(robot_nc < M && map[robot_r][robot_nc] == 0) {
                robot_c = robot_nc;
                second();
            }
            else if(map[robot_r][robot_nc] == 1){
                world_flag = true;
                return;
            }
        }
    }
}