[백준] 14503번 : 로봇청소기 (JAVA/자바)

[문제 링크]

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

문제 설명

0-청소X, 1-벽

청소기가 작동하는 순서는 아래와 같다.
1. 현재 칸이 아직 청소되지 않은 경우, 현재 칸 청소
2. 현재 칸 주변 4칸 중 청소되지 않은 빈 칸이 없는 경우(4칸이 모두 청소된 경우)
    2-1. 바라보는 방향 기준 한 칸 후진할  수 있다면, 후진 후 1으로 돌아감
    2-2. 후진할 수 없는 경우(벽인 경우) stop
3. 현재 칸 주변 4칸 중 청소되지 않은 빈 칸이 있는 경우
    3-1. 청소기 반시계방향으로 90도 회전
    3-2. 바라보는 방향 기준 앞쪽 칸이 청소되지 않은 경우, 한 칸 전진

    3-3. 1으로 돌아감 

 

 

 

문제 풀이

알고리즘 분류

• 구현

문제에 주어진 청소기 작동 순서대로 구현하면 된다.

청소가 되지 않은 칸은 0, 청소가 된 칸은 -1, 벽인 칸은 1 로 구분한다.

 

처음에는 청소가 된 칸과 벽인 칸을 둘 다 "로봇청소기가 갈 수 없는 공간"으로 생각해서 똑같이 1로 처리했었다.

하지만 이렇게 하면 4칸 중 청소되지 않은 빈칸이 없는 경우 한 칸 후진을 해야하는데, 후진을 할 수 있는지 없는지 알 수 없다.(후진할 칸이 청소가 된 칸이면 후진 가능, 벽이면 후진 불가능) 

전체코드

import java.io.*;
import java.util.*;

public class Main {

    static int n, m, r, c, d, count = 0;
    static int[][] rooms;
    static int[] dr = {-1, 0, 1, 0}; //북, 동, 남, 서
    static int[] dc = {0, 1, 0, -1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
        d = Integer.parseInt(st.nextToken()); //방향

        rooms = new int[n][m];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                rooms[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        clean();
        System.out.println(count);
    }

    public static void clean() {
        while(true) {
            //현재 칸이 청소되지 않은 경우 현재 칸 청소
            if (rooms[r][c] == 0) {
                rooms[r][c] = -1;   //청소완료 상태로 변경
                count++;    //청소횟수 증가
            }

            int cleanCnt = 0;   //이미 청소된 칸 or 벽의 개수
            
            //현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 있는지 탐색
            for (int i = 0; i < 4; i++) {
                d = (d == 0) ? 3 : d - 1; //반시계방향으로 90도 회전

                int nr = r + dr[d];
                int nc = c + dc[d];

                //방의 범위를 벗어나는 경우
                if(nr < 0 || nc < 0 || nr >= n || nc >= m)  continue;

                //이미 청소된 칸이거나 벽일 경우
                if (rooms[nr][nc] == 1 || rooms[nr][nc] == -1)  cleanCnt++;

                //청소되지 않은 빈 칸이 있는 경우 한 칸 전진
                if(rooms[nr][nc] == 0) {
                    r = nr;
                    c = nc;
                    break;
                }
            }

            //주변 4칸 중 청소되지 않은 빈 칸이 없는 경우
            if(cleanCnt == 4) {
                int nr = r - dr[d];
                int nc = c - dc[d];

                //범위를 벗어나거나 뒤쪽이 벽이라 후진할 수 없는 경우
                if(nr < 0 || nc < 0 || nr >= n || nc >= m || rooms[nr][nc] == 1) {
                    return;
                }
                //한 칸 후진
                r = nr;
                c = nc;
            }
        }

    }
}