[Algorithm/Java] 백준 14503번 - 로봇청소기

---

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

---

🔍 문제 풀이

Flowchart

핵심 로직

반시계 방향으로 회전

d = (d + 3) % 4; // 반시계 방향으로 회전

헷갈린점

회전 조건

“현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 있는 경우, 반시계 방향으로 회전한다.”라는 조건이 헷갈렸다.

처음엔 “청소되지 않은 칸이 있는 게 확실해야 회전을 하는 거구나”라고 해석해 주변 4칸을 한 번에 검사한 다음, 청소할 곳이 있으면 그때 회전하려고 했다.

하지만 근데 청소되지 않은 칸이 있는지 확인하기 위해서 회전부터 했어야한다.

로봇은 아래처럼 움직인다.

1. 무조건 반시계 방향으로 회전
2. 회전한 방향의 앞 칸을 확인
3. 청소되지 않은 칸이면 전진하고 다시 반복
4. 위 과정을 4번 반복하며 주변을 탐색한다

문제 문장은 마치 조건 -> 회전처럼 보이지만 실제는 회전 -> 조건 확인 -> 전진 판단 순으로 진행해야한다.

또한, 청소 가능한 칸이 보이면, 바로 전진하고 탐색 종료해야 한다.

💻 전체 코드

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

public class Main {
    static int n, m, r, c, d;
    static int[][] room;
    static int count;

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

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

        room = new int[n][m];

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

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

        cleanRoom();
        System.out.println(count);
    }

    // 0(빈칸), 1(벽), 2(청소 완료)
    static void cleanRoom(){
        while(true){
            // 현재칸이 청소 되어있지 않으면 -> 현재칸 청소
            if(room[r][c] != 2){
                room[r][c] = 2;
                count ++;
            }

             boolean isCleaned = false; // 청소할 칸 찾았는가

            // 회전하며 현재 칸 주변 4칸 확인
            for(int i=0; i<4; i++){
                d = (d + 3) % 4; // 반시계 방향으로 회전
                int nx = r + dx[d];
                int ny = c + dy[d];

                if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                if(room[nx][ny] == 0){ // 앞 칸이 빈칸이면
                    // 한 칸 전진 후 처음으로
                    r = nx;
                    c = ny;
                    isCleaned = true;
                    break; // 다음 while 루프로
                }
            }

            // 4방향 반복하고 청소할 칸 못 찾았으면 -> 후진
            if(!isCleaned){ // 청소할 칸 없으면
                // 후진 좌표 계산
                int backX = r - dx[d];
                int backY = c - dy[d];

                if(room[backX][backY] == 1){
                    return; // 벽이면 종료
                }else{
                    r = backX;
                    c = backY;
                }
            }
        }
    }
}