[백준] 14503번 Java (구현, 시뮬레이션)

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

💡문제

풀이

접근법 : 로봇 청소기가 작동하는 순서대로 구현하는 게 제일 편하다.
현재 칸이 아직 청소되지 않은 경우 -> 청소한다.

            if(!cleaned[x][y]){
                cleaned[x][y] = true;
                cleanCount++;
            }

주변 칸 중 청소되지 않은 빈 칸이 있는 경우

            boolean cleanedAll = true;
            for (int i = 0; i < 4; i++) {
                int nd = (d+3) % 4; // 왼쪽으로 90도 돌기
                int nx = x + dx[nd];
                int ny = y + dy[nd];
                // 벽이 아니고 청소되지 않은 경우
                if(nx>=0 && ny>=0 && nx<n && ny<m && !cleaned[nx][ny] && room[nx][ny] == 0){
                    x = nx;
                    y = ny;
                    d = nd;
                    cleanedAll = false;
                    break;
                }
                // 방향 변경 후 다시 for문 돌리기
                d = nd;
            }

• 반시계 방향으로 회전한다.
• 바라보는 방향으로 앞쪽 칸이 청소 X칸 인 경우 한 칸 전진한다.
• 주변 칸이 모두 청소되었는지 boolean cleanedAll 로 확인
  
  

주변 칸 중 청소되지 않은 빈 칸이 없는 경우

            if(cleanedAll) {
                int back = (d + 2) % 4; // 후진 방향
                int bx = x + dx[back];
                int by = y + dy[back];
                // 후진할 좌표가 벽이 아님
                if (bx >= 0 && by >= 0 && bx < n && by < m && room[bx][by] == 0) {
                    x = bx;
                    y = by;
                } else {
                    // 후진할 수 없는 경우 종료
                    break;
                }
            }
        }
        return cleanCount;
    }

• 한 칸 후진할 수 있다면 후진하고 처음으로 돌아간다.
• 뒤쪽 칸이 벽이라 후진할 수 없다면 작동을 멈춘다.

내 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int[] dx = {-1,0,1,0};   //북 동 남 서
    static int[] dy = {0,1,0,-1};
    static int[][] room;
    static boolean[][] cleaned;
    static int n,m;

    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());
        int r = Integer.parseInt(st.nextToken());   
        int c = Integer.parseInt(st.nextToken());
        int d = Integer.parseInt(st.nextToken());   // 최초 방향

        room = new int[n][m];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                room[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        System.out.println(robotClean(r,c,d));
    }
    
    static int robotClean(int x, int y, int d){
        int cleanCount = 0;
        cleaned = new boolean[n][m];
        while(true){

            // 1. 현재 칸이 아직 청소되지 않은 경우 -> 청소
            if(!cleaned[x][y]){
                cleaned[x][y] = true;
                cleanCount++;
            }
            // 2. 주변 칸 중 청소되지 않은 빈 칸이 있는 경우
            boolean cleanedAll = true;
            for (int i = 0; i < 4; i++) {
                int nd = (d+3) % 4; // 왼쪽으로 90도 돌기
                int nx = x + dx[nd];
                int ny = y + dy[nd];
                // 벽이 아니고 청소되지 않은 경우
                if(nx>=0 && ny>=0 && nx<n && ny<m && !cleaned[nx][ny] && room[nx][ny] == 0){
                    x = nx;
                    y = ny;
                    d = nd;
                    cleanedAll = false;
                    break;
                }
                // 방향 변경 후 다시 for문 돌리기
                d = nd;
            }

            // 3. 주변 칸 중 청소되지 않은 빈 칸이 없는 경우
            if(cleanedAll) {
                int back = (d + 2) % 4; // 후진 방향
                int bx = x + dx[back];
                int by = y + dy[back];
                // 후진할 좌표가 벽이 아님
                if (bx >= 0 && by >= 0 && bx < n && by < m && room[bx][by] == 0) {
                    x = bx;
                    y = by;
                } else {
                    // 후진할 수 없는 경우 종료
                    break;
                }
            }
        }
        return cleanCount;
    }
}

• 차분하게 순서에 따라서 풀면 구현할 수 있는 문제였다.
• 시간이 오래 걸렸다.