[백준][Java] 14503번 로봇 청소기 풀이 (구현, 시뮬레이션)

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

14503번: 로봇 청소기

 

dfs 방식으로 문제를 해결해보았습니다.

그리고 2차원 배열 map 의 원소는 다음 세가지로 정했습니다.

(청소기의 방문 체크를 위해서 체크배열을 굳이 만들지 않음)

0 : 청소해야할 빈 칸

1 :  청소기가 지나가지 못하는 벽

2 : 청소기가 지나갈 수는 있으나, 이미 청소한 칸

---

direction 이라는 int형 변수를 통해서 0부터 3까지를 북,동,남,서로 정합니다.

dx[] 와 dy[]의 인덱스에 0부터 3까지 들어갈텐데

북동남서의 순서로 탐색할 수 있도록 dx, dy의 원소를 초기화합니다.

ex) direction이 2일 때는 남쪽 : 열은 그대로, 행만 한칸 밑으로 내려서 탐색

       ->  dx[2] = 1, dy[2] = 0 이 되어야 함.

---

탐색의 종료조건 :  방향 그대로, 후진한 칸의 Map 값이 1일 때

-> 주변 4칸 중 청소되지 않은 빈 칸이 없어서 방향을 유지한 채로 후진해야하는데, 

     바라보는 방향의 뒤쪽 칸이 벽이라 후진할 수 없다면

---

반시계 90도 회전하는 부분 중요합니다.

direction을 dx와 dy의 인덱스로 넘겨서 0부터 3까지 돌리면서 사용하고싶은 상홥입니다.

왜냐하면 주변 4칸중 청소할 칸이 있는데, 그 청소할 칸의 방향을 찾기위해서 청소기가

4방향을 360도 돌아서 탐색해보도록 만들어야하기 때문이죠.

 

북쪽(0) -> 서쪽(3)

서쪽(3) -> 남쪽(2)

남쪽(2) -> 동쪽(1)

동쪽(1) -> 북쪽(0)

처럼 direction에 적절한 연산을 해서 좌변에서 우변으로 만들어주는게 목표입니다.

1을 차감하면되는데, 북쪽(0) -> 서쪽(3) 의 상황을 추가적으로 생각해줘야합니다.

따라서 3을 더한 후 4로 나눈 나머지 연산을 해줍니다.

direction = (direction + 3) % 4;

---

package WEEK0.P14503;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int N;
    static int M;
    static int[][] map; //0이면 청소 전, 1이면 벽, 2이면 청소 후
    //방향은 후진 기준으로 0부터 3까지 차례대로 배치
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};
    static int startX, startY, direction;
    static int ans = 0;

    public static void main(String[] args) throws IOException {
      //  System.setIn(new FileInputStream("src/WEEK0/P14503/input.txt"));

        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];
        st = new StringTokenizer(br.readLine());
        startX = Integer.parseInt(st.nextToken());
        startY = Integer.parseInt(st.nextToken());
        direction = Integer.parseInt(st.nextToken());

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

        if(map[startX][startY] == 0){
            map[startX][startY] = 2;
            ans++;
        }

        search(startX, startY, direction);

        System.out.println(ans);
    }

    static void search(int x, int y, int direction){
        if(map[x][y] == 0){
            map[x][y] = 2;
            ans++;
        }

        //현재 칸의 주변 4칸 확인
        int flag = 0;
        for(int i = 0; i < 4; i++){
            int xx = x + dx[i];
            int yy = y + dy[i];
            if(0 <= xx && xx < N && 0 <= yy && yy < M
                    && map[xx][yy] == 0){
                flag = 1;
            }
        }

        if(flag == 1){  //현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 있는 경우
            //System.out.println(x + "," + y + " 에서 주변에 빈 칸 있다");
            direction = (direction + 3) % 4;  //중요. 반시계 90도 회전
            int xx = x + dx[direction];
            int yy = y + dy[direction];

            // 청소하지 않은 칸 만날떄까지 회전시켜주기
            while(map[xx][yy] != 0){
                direction = (direction + 3) % 4;
                xx = x + dx[direction];
                yy = y + dy[direction];
            }

            if(0 <= xx && xx < N && 0 <= yy && yy < M
                    && map[xx][yy] == 0){
                map[xx][yy] = 2;
                ans++;
                //printmap();

                search(xx, yy, direction);
            }
        } else {    //현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 없는 경우
            //System.out.println(x + "," + y + " 에서 주변에 빈 칸 없다");
            int xx = x - dx[direction];
            int yy = y - dy[direction];
            if(0 <= xx && xx < N && 0 <= yy && yy < M
                    && map[xx][yy] != 1){
                //바라보는 방향을 유지한 채로 한 칸 후진할 수 있다면 한 칸 후진하고 1번으로 돌아간다.
                search(xx, yy, direction);
            }else{
                //바라보는 방향의 뒤쪽 칸이 벽이라 후진할 수 없다면 작동을 멈춘다.
                //printmap();
            }
        }
    }

    static void printmap(){
        for(int i = 0; i < N; i++){
            for(int j = 0; j < M; j++){
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println();
    }
}