[ 백준 ] 14503 로봇 청소기

📌 Problem

로봇 청소기의 청소/이동 조건에 따라 몇 개의 공간을 청소했는지 출력하면 되는 문제이다. 공간은 N x M의 크기를 가지며 각각의 공간은 청소가 되어 있지 않은 상태 0과 로봇이 이동할 수 없는 벽인 상태 1로 되어 있다. 로봇의 시작 위치와 방향이 주어지면 청소를 시작한다. 로봇 청소기 알고리즘은 다음과 같다.

Step 1. 현재 위치한 공간이 청소가 되어 있지 않다면 청소를 한다.
Step 2. 주변 공간(동서남북) 중에 청소하지 않은 공간이 있다면 다음을 실행한다.
Step 2-1. 바라보고 있는 방향 기준 왼쪽으로 90도 회전한다. (바라보는 방향을 변경한다.)
Step 2-2. 앞의 공간이 청소되어 있지 않다면 앞으로 전진하고 Step 1으로 돌아간다.
Step 3. 주변 공간 중에 청소하지 않은 공간이 없다면 다음을 실행한다.
Step 3-1. 바라보고 있는 방향 기준 뒤로 이동한다. (바라보는 방향은 변경하지 않고 후진만 한다.)
Step 3-2. 후진하는 위치에 벽이 있어서 후진이 불가능하다면 로봇 청소기는 종료된다.

📌 Solution

Step 0. 필요한 자료구조를 초기화한다.
moves는 각각 북동남서 방향으로 한 칸 이동하는 동작이다. robot은 현재 row, col, direction 정보를 가지고 있다. map은 전체 공간의 상태이다. 0은 미청소 상태, 1은 벽, 2는 청소 완료 상태이다.

private final int[][] moves = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
int[] robot;
int[][] map;

Step 1. 청소를 한다.

int cleaned = 0;                                    // 청소 횟수
while (true) {                                      // 청소가 끝날때까지 반복
    if (map[robot[0]][robot[1]] == 0) cleaned++;    // 미청소 공간이면 청소
    map[robot[0]][robot[1]] = 2;                    // 청소 완료 상태로 변경
    if (checkAround()) continue;                    // 주변에 미청소 공간이 있으면 이동
    if (checkBack()) break;                         // 뒤로 이동할 수 없다면 청소 종료
}

Step 2. checkAround() 주변 확인하기
공간 밖으로 나가는 것을 고려하여 try-catch 사용 (ignore를 통해 예외 무시)

for (int m = 0; m < 4; m++) {                   // 4방향 확인
    robot[2] = (robot[2] + 3) % 4;              // 바라보는 방향 회전
    try {
        // 앞 공간이 미청소 상태이면 이동
        if (map[robot[0] + moves[robot[2]][0]][robot[1] + moves[robot[2]][1]] == 0) {
            robot[0] += moves[robot[2]][0];
            robot[1] += moves[robot[2]][1];
            return true;
        }
    } catch (ArrayIndexOutOfBoundsException ignore){
    }
}
// 4방향 모두 청소 완료 or 벽
return false;

Step 3. checkBack() 뒤로 이동하기
공간 밖으로 나가는 것을 고려하여 try-catch 사용 (예외가 발생하면 청소 종료)

try {
    // 뒤로 이동할 수 있다면 뒤로 이동
    if (map[robot[0] + moves[(robot[2] + 2) % 4][0]][robot[1] + moves[(robot[2] + 2) % 4][1]] != 1) {
        robot[0] += moves[(robot[2] + 2) % 4][0];
        robot[1] += moves[(robot[2] + 2) % 4][1];
    } else return true;
} catch (ArrayIndexOutOfBoundsException e) {
    return true;
}
// 뒤가 벽이거나 공간 밖이면 청소 종료
return false;

📌 Code

private final int[][] moves = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

int[] robot;
int[][] map;

public void solve() throws IOException {
    init();
    result.append(cleanUp());
}

private int cleanUp() {
    int cleaned = 0;                                    // 청소 횟수
    while (true) {                                      // 청소가 끝날때까지 반복
        if (map[robot[0]][robot[1]] == 0) cleaned++;    // 미청소 공간이면 청소
        map[robot[0]][robot[1]] = 2;                    // 청소 완료 상태로 변경
        if (checkAround()) continue;                    // 주변에 미청소 공간이 있으면 이동
        if (checkBack()) break;                         // 뒤로 이동할 수 없다면 청소 종료
    }
    return cleaned;
}

private boolean checkAround() {
    for (int m = 0; m < 4; m++) {                   // 4방향 확인
        robot[2] = (robot[2] + 3) % 4;              // 바라보는 방향 회전
        try {
            // 앞 공간이 미청소 상태이면 이동
            if (map[robot[0] + moves[robot[2]][0]][robot[1] + moves[robot[2]][1]] == 0) {
                robot[0] += moves[robot[2]][0];
                robot[1] += moves[robot[2]][1];
                return true;
            }
        } catch (ArrayIndexOutOfBoundsException ignore){
        }
    }
    // 4방향 모두 청소 완료 or 벽
    return false;
}

private boolean checkBack() {
    try {
        // 뒤로 이동할 수 있다면 뒤로 이동
        if (map[robot[0] + moves[(robot[2] + 2) % 4][0]][robot[1] + moves[(robot[2] + 2) % 4][1]] != 1) {
            robot[0] += moves[(robot[2] + 2) % 4][0];
            robot[1] += moves[(robot[2] + 2) % 4][1];
        } else return true;
    } catch (ArrayIndexOutOfBoundsException e) {
        return true;
    }
    // 뒤가 벽이거나 공간 밖이면 청소 종료
    return false;
}

private void init() throws IOException {
    StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
    int N = Integer.parseInt(tokenizer.nextToken());
    int M = Integer.parseInt(tokenizer.nextToken());
    robot = Arrays.stream(reader.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
    map = new int[N][M];

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