[백준] 14503번: 로봇 청소기 - java

문제

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

14503번: 로봇 청소기

 

접근법

쉬운 구현 문제이다. 동서남북~ 에서 BFS를 사용하라는 것을 대놓고 보여준다. 문제에서 주는 작동 방식을 정말 그.대.로 구현하면 된다. 주의할 점은 방향을 다루는 것인데 문제에서 제시한 방향은 0북 1동 2남 3서 이지만 반시계 방향으로 회전하는 것은 북->서->남->동 이기 때문에 잘 처리해주어야 한다. 나 같은 경우 dir 배열을 0북 1동 2남 3서 그대로 만들고, 인덱스를 거꾸로 가도록 구현하였다. 후진은 어떻게 처리할지 고민해보면 좋을 것 같다. (if문을 덕지덕지 만들어 구현할 순 있지만 조금 더 간단한 방법은 없을지~?)

 

코드

import java.awt.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

public class Main {

    static int N, M, d;
    static Point start;
    static int[][] room; // 0: 빈 칸 / 1: 벽 / 2: 청소 완료

    static int[] dirR = {-1, 0, 1, 0}; // 북 동 남 서
    static int[] dirC = {0, 1, 0, -1}; // 북 동 남 서

    static int answer = 0;

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

        st = new StringTokenizer(br.readLine());
        start = new Point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        d = Integer.parseInt(st.nextToken());

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

        cleaning();

        System.out.println(answer);
    }

    private static void cleaning() {
        Deque<Point> queue = new ArrayDeque<>();
        queue.offer(start);

        while (!queue.isEmpty()) {
            Point now = queue.poll();

            // 1. 현재 칸이 아직 청소되지 않은 경우, 현재 칸을 청소한다.
            if (room[now.r][now.c] == 0) {
                room[now.r][now.c] = 2;
                answer++;
            }

            // 현재 칸의 주변 4칸이 모두 청소 됐는지 체크
            boolean allClean = true;

            for (int i = 0; i < 4; i++) {
                // 반시계 방향으로 회전
                d = (d - 1) < 0 ? 3 : (d - 1);

                // 앞쪽 칸이 청소되지 않은 빈 칸인 경우 한 칸 전진
                int r = now.r + dirR[d];
                int c = now.c + dirC[d];

                if (rangeIn(r, c) && room[r][c] == 0) {
                    queue.offer(new Point(r, c));
                    allClean = false;
                    break;
                }
            }

            // 주변 4칸 중 청소되지 않은 빈 칸이 없는 경우
            if (allClean) {
                // 한 칸 후진한 위치
                int r = now.r + dirR[d] * -1;
                int c = now.c + dirC[d] * -1;

                // 후진할 수 없는 경우 작동을 멈춘다.
                if (!rangeIn(r, c) || room[r][c] == 1) {
                    break;
                } else {
                    queue.offer(new Point(r, c));
                }
            }
        }
    }

    private static boolean rangeIn(int r, int c) {
        return (r >= 0) && (c >= 0) && (r < N) && (c < M);
    }

    static class Point {
        int r, c;

        public Point(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }
}

나는 후진할 때 -1을 곱해서 반대 방향으로 이동해주었다. 이때 방향은 그대로 유지해야되기 때문에 d(방향을 나타내는 변수)의 값은 그대로 유지되어야 한다.