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

문제 링크

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

문제 풀이

시뮬레이션은 문제를 이해하는게 너무 힘들다. 문제가 이상한건지 내가 이상한건지...
문제를 순서대로 이해하는것부터 시작했고, bfs로 접근하면 되겠구나 까진 떠올랐다.
map[n][m] 에 색칠한 안한 부분이0, 벽이1, 색칠한 부분이2 사실상 chk[n][m]은 필요가 없었다는 생각이 든다.

그리고 시작위치를 정해주므로 초기 시작위치와 방향을 가지고 bfs를 시작한다.
초기 위치를 queue에 넣고 chk를 이때는 사용해야겠다는 생각이 들어서 true로 map의 값을 2로 바꿔주었다.

기본의 bfs와 같지만 몇가지 다른점이 있었다. 탐색해야 하는 방향을 주어주었기에 그 방향에 맞춰서 for문을 돌았는데 그 방향은 왼쪽으로 탐색 = 시계 반대 방향이라서

    static int[] diry = {-1, 0, 1, 0, -1, 0, 1, 0};
    static int[] dirx = {0, 1, 0, -1, 0, 1, 0, -1};

똑같은 부분을 2번 반속시켰고, 시작방향에 +4를 해주었고 거기서 부터 --를 하면 4번 반복했다.(4방향 탐색), 그리고 탐색을 해서 그 방향에 청소할 곳이 있다면 탐색을 멈추고 그곳으로 이동한다. 그래서 checker2를 사용하여 탐색에 성공했다면 다시 처음으로 돌아가게 했다.

만약 checker2가 false라면 4방향 모두 청소가 되어있거나, 벽인 경우이다.
case문을 사용하여 바라보는 방향의 뒤쪽이 벽인경우를 확인해서 벽이면 checker를 false로 바꿔서 탐색을 종료시키는 조건으로 만들었고, 뒤가 벽이 아닌경우 그 칸으로 이동시키도록 하였다.

코드

package simulation;

import java.util.*;

public class BJ14503 {

    static int n;
    static int m;
    static int[][] map;
    static boolean[][] chk;

    static int[] diry = {-1, 0, 1, 0, -1, 0, 1, 0};
    static int[] dirx = {0, 1, 0, -1, 0, 1, 0, -1};

    static int answer = 0;

    static class Node {
        int y;
        int x;
        int dir;

        public Node(int y, int x, int dir) {
            this.y = y;
            this.x = x;
            this.dir = dir;
        }
    }

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        m = sc.nextInt();
        map = new int[n][m];
        chk = new boolean[n][m];

        int start_y = sc.nextInt();
        int start_x = sc.nextInt();
        int start_dir = sc.nextInt();

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                map[i][j] = sc.nextInt();
            }
        }

        bfs(start_y, start_x, start_dir);
        System.out.println(answer);
    }

    public static void bfs(int y, int x, int dir) {
        Queue<Node> queue = new LinkedList<>();
        queue.add(new Node(y, x, dir));
        //현재 위치를 청소한다.
        chk[y][x] = true;
        map[y][x] = 2;
        answer++;
        boolean checker = true;
        
        while (!queue.isEmpty() && checker) {
            boolean checker2 = false;
            Node now = queue.poll();
            //왼쪽으로 꺾음
            int now_dir = now.dir == 0 ? 3 : now.dir - 1;

            // 현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다.
            for (int i = now_dir + 4; i > now_dir; i--) {
                int now_y = now.y + diry[i];
                int now_x = now.x + dirx[i];

                if (now_y >= 0 && now_y < n && now_x >= 0 && now_x < m) {
                    if (!chk[now_y][now_x] && map[now_y][now_x] == 0) {
                        // 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.
                        queue.add(new Node(now_y, now_x, i % 4));
                        answer++;
                        map[now_y][now_x] = 2;
                        chk[now_y][now_x] = true;
                        checker2 = true;
                        break;
                    } else {
                        //왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.
                    }
                }
            }//for - end
            if(checker2){
                continue;
            }
//            네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.
//            네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.

            switch (now.dir) {
                case 0:
                    now.y++;
                    if (map[now.y][now.x] == 1) {
                        checker = false;
                    } else {
                        queue.add(new Node(now.y, now.x, now.dir));
                    }
                    break;
                case 1:
                    now.x--;
                    if (map[now.y][now.x] == 1) {
                        checker = false;
                    } else {
                        queue.add(new Node(now.y, now.x, now.dir));
                    }
                    break;
                case 2:
                    now.y--;
                    if (map[now.y][now.x] == 1) {
                        checker = false;
                    } else {
                        queue.add(new Node(now.y, now.x, now.dir));
                    }
                    break;
                case 3:
                    now.x++;
                    if (map[now.y][now.x] == 1) {
                        checker = false;
                    } else {
                        queue.add(new Node(now.y, now.x, now.dir));
                    }
                    break;
            }
        }
    }
}