[백준/Java] #14503 로봇 청소기

로봇 청소기 (14503번)

사용 언어 : Java
레벨 : 골드5
📎 https://www.acmicpc.net/problem/14503

14503번: 로봇 청소기

 

❓ 접근

문제를 보자마자 그동안 풀어본 BFS 문제 풀이들을 약간 바꿔서 사용하면 되겠다 생각했다. 

 

1. 현재 칸이 청소되지 않은 경우, 현재 칸을 청소한다.

2. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 없는 경우

• 바라보는 방향을 유지한 채로 한 칸 후진할 수 있다면 한 칸 후진하고 1번으로 돌아간다.
• 바라보는 방향의 뒤쪽 칸이 벽이라 후진할 수 없다면 작동을 멈춘다.

3. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 있는 경우

• 반시계 방향으로 90도 회전한다.
• 바라보는 방향을 기준으로 앞쪽 칸이 청소되지 않은 빈 칸인 경우 한 칸 전진한다.
• 1번으로 돌아간다.

 

우선 주의할 점이 있는데 주변에 4칸 중 청소되지 않은 빈 칸이 하나라도 있는 경우 무조건 반시계 방향으로 90도를 회전해야 한다. 나는 처음에 이 조건을 생각하지 않고 구현을 해서 바라보는 방향의 앞쪽 칸이 청소되지 않은 칸이면 바로 이동을 하도록 해서 예제를 틀렸었는데 이 부분을 고려하지 않았기 때문이였다.

 

✏️ 풀이

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BOJ14503 {
    static int N, M;
    static int r, c, d, count;
    static int[][] room;

    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());
        r = Integer.parseInt(st.nextToken()); // x 좌표
        c = Integer.parseInt(st.nextToken()); // y 좌표
        d = Integer.parseInt(st.nextToken()); // 방향(0 : 위, 1 : 오른쪽, 2 : 아래, 3 : 왼쪽)
        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());
            }
        }

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

    static void solution() {
        int[][] dist = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // d의 방향과 동일
        while (true) {
            // 인접한 칸에 청소하지 않은 칸이 있는지 체크하는 변수
            boolean check = false;
            // 현재 칸이 청소되어 있지 않다면 청소
            if (room[r][c] == 0) {
                room[r][c] = 2;
                count++;
            }

            // 인접한 칸 중 청소하지 않은 칸이 있으면 무조건 반시계 90도로 돌거기 때문에 d - 1부터 시작
            for (int i = d - 1; i > d - 5; i--) {
                // dist의 반대방향으로 움직일거기 때문에 i-- 해주고 배열의 크기를 벗어나지 않도록 +4 %4를 해줌
                int nx = r + dist[(i + 4) % 4][0];
                int ny = c + dist[(i + 4) % 4][1];
                if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
                // 다음으로 이동할 위치가 이미 청소 되어있거나, 벽일 경우 다음 90도 확인
                if (room[nx][ny] > 0) continue;
                // 여기까지 오면 앞칸이 청소할 칸이니까 체크해주고 그 칸으로 이동해서 좌표 갱신
                check = true;
                r = nx;
                c = ny;
                // 방향도 갱신해줌
                d = (i + 4) % 4;
                // 더 이상 볼필요 없으니 break
                break;
            }
            if (!check) {
                // 만약 인접한 칸 중 청소할 수 있는 칸이 없을 경우
                // 후진
                r += dist[(d + 2) % 4][0];
                c += dist[(d + 2) % 4][1];
                // 배열의 크기를 벗어나거나 벽일 경우 while문 종료
                if (r < 0 || r >= N || c < 0 || c >= M || room[r][c] == 1) break;
            }
        }
    }
}

 

BFS 문제를 풀 수 있다면 어렵지 않게 풀 수 있는 문제였던 것 같다! 로봇이 청소할 때마다 출력을 확인해서 잘 작동하는지 확인했는데 진짜 로봇 청소기를 돌리는 느낌이라 재밌었다 ㅎㅎ