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

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

 

 

 

로봇 청소기

 

 

1)  문제

로봇 청소기와 방의 상태가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오.

로봇 청소기가 있는 방은 
N x M 크기의 직사각형으로 나타낼 수 있으며, 
1 x 1 크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다.
청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북 중 하나이다.
방의 각 칸은 좌표 (r, c)로 나타낼 수 있고,
가장 북쪽 줄의 가장 서쪽 칸의 좌표가 (0, 0),
가장 남쪽 줄의 가장 동쪽 칸의 좌표가 (N-1, M-1)이다.
즉, 좌표 (r, c)는 북쪽에서 (r+1)번째에 있는 줄의 서쪽에서 (c+1)번째 칸을 가리킨다.
처음에 빈 칸은 전부 청소되지 않은 상태이다.

로봇 청소기는 다음과 같이 작동한다.
현재 칸이 아직 청소되지 않은 경우, 현재 칸을 청소한다.
현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 없는 경우,
바라보는 방향을 유지한 채로 한 칸 후진할 수 있다면 한 칸 후진하고 1번으로 돌아간다.
바라보는 방향의 뒤쪽 칸이 벽이라 후진할 수 없다면 작동을 멈춘다.
현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 있는 경우,
반시계 방향으로 90도 회전한다.
바라보는 방향을 기준으로 앞쪽 칸이 청소되지 않은 빈 칸인 경우 한 칸 전진한다.
1번으로 돌아간다.

입력: 첫째 줄에 방의 크기 N과 M이 입력된다. ( 3 <= N, M <= 50  )
둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 (r, c)와 처음에 로봇 청소기가 바라보는 방향 d가 입력된다. 
d가 0인 경우 북쪽, 1인 경우 동쪽, 2인 경우 남쪽, 3인 경우 서쪽을 바라보고 있는 것이다.

셋째 줄부터 N개의 줄에 각 장소의 상태를 나타내는 N x M개의 값이 한 줄에 M개씩 입력된다. 
i번째 줄의 j번째 값은 칸 (i, j)의 상태를 나타내며, 이 값이 0인 경우 (i, j)가 청소되지 않은 빈 칸이고, 
1인 경우 (i, j)에 벽이 있는 것이다.
방의 가장 북쪽, 가장 남쪽, 가장 서쪽, 가장 동쪽 줄 중 하나 이상에 위치한 모든 칸에는 벽이 있다.
로봇 청소기가 있는 칸은 항상 빈 칸이다.

출력: 로봇 청소기가 작동을 시작한 후 작동을 멈출 때까지 청소하는 칸의 개수를 출력한다.

N M          // 방 크기 (N행 × M열)
r c d        // 로봇 위치 (r,c) 및 바라보는 방향 d
map[][]      // 방의 상태 (0=빈칸, 1=벽)

 

 

 

 

2)  예시

예제입력 1:

3 3
1 1 0
1 1 1
1 0 1
1 1 1

예제출력 1: 

1

 

 

예제입력 2:

11 10
7 4 0
1 1 1 1 1 1 1 1 1 1
1 0 0 0 0 0 0 0 0 1
1 0 0 0 1 1 1 1 0 1
1 0 0 1 1 0 0 0 0 1
1 0 1 1 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 1 0 1
1 0 0 0 0 0 1 1 0 1
1 0 0 0 0 0 1 1 0 1
1 0 0 0 0 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1

 

예제출력 2:

57

 

 

 

 

3)  풀이

 

* 시뮬레이션 문제일까?

시뮬레이션 문제 특징	로봇청소기 문제와 일치 여부
규칙이 명확하게 서술됨	청소 → 회전 → 이동 → 후진 순서
수학적 풀이보다 구현력이 중요	방향 회전, 맵 탐색, 상태 관리 필요
조건 분기와 상태 추적이 핵심	4방향 확인, 청소 여부 저장
실제 상황을 재현해야 함	로봇이 움직이는 것을 그대로 구현해야 함

 

 

* 시뮬레이션 문제라는 걸 파악하는 기준
1. 이동한다, 회전한다, 청소한다, 뒤로 간다 등
→ 현실에서 일어나는 행동을 그대로 따라야 한다면 시뮬레이션 문제

2. 문제 설명이 명확한 단계로 나뉘어져 있고,
그 흐름을 조건문 + 반복문으로 재현해야 한다면 시뮬레이션

3. 정답을 구하는 수식이나 최적화 알고리즘이 없고,
그냥 문제에서 하라는 대로 코드를 써 내려가야 한다면 시뮬레이션

 

 

 

4)  코드

import java.util.Scanner;
// 사용자 입력을 받기 위한 Scanner 클래스 임포트

public class Main {
    static int N, M;                   // 방의 크기 (N행 × M열)
    static int[][] map;               // 방의 상태 (0: 빈칸, 1: 벽)
    static boolean[][] cleaned;       // 청소 여부 저장 배열
    static int[] dx = {-1, 0, 1, 0};   // 방향 배열 (북, 동, 남, 서)
    static int[] dy = {0, 1, 0, -1};   // 방향 배열 (북, 동, 남, 서)
    static int count = 0;             // 청소한 칸의 수

    public static void dfs(int x, int y, int dir) {
        // 현재 칸이 청소되지 않았다면 청소
        if (!cleaned[x][y]) {
            cleaned[x][y] = true;
            count++;
        }

        // 4방향 탐색 (왼쪽부터 반시계 방향 회전)
        for (int i = 0; i < 4; i++) {
            dir = (dir + 3) % 4; // 왼쪽 방향으로 회전
            int nx = x + dx[dir];
            int ny = y + dy[dir];

            // 맵 범위 내이고, 빈 칸이며 청소되지 않았다면 이동
            if (nx >= 0 && ny >= 0 && nx < N && ny < M) {
                if (map[nx][ny] == 0 && !cleaned[nx][ny]) {
                    dfs(nx, ny, dir);  // 이동한 위치에서 다시 시뮬레이션 시작
                    return;            // 한 번 이동하면 즉시 리턴 (다시 현재 칸으로 돌아오지 않음)
                }
            }
        }

        // 네 방향 모두 청소 불가 → 후진 시도
        int back = (dir + 2) % 4;      // 반대 방향 계산
        int bx = x + dx[back];
        int by = y + dy[back];

        // 후진 가능하면 이동 (방향은 유지)
        if (bx >= 0 && by >= 0 && bx < N && by < M && map[bx][by] == 0) {
            dfs(bx, by, dir);
        }
        // 후진 불가(벽)일 경우 재귀 종료 → 작동 종료
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();  // 방의 행 수
        M = sc.nextInt();  // 방의 열 수
        int x = sc.nextInt();  // 로봇의 시작 위치 x
        int y = sc.nextInt();  // 로봇의 시작 위치 y
        int d = sc.nextInt();  // 로봇의 시작 방향

        map = new int[N][M];
        cleaned = new boolean[N][M];

        // 방 상태 입력
        for (int i = 0; i < N; i++)
            for (int j = 0; j < M; j++)
                map[i][j] = sc.nextInt();

        dfs(x, y, d);  // 로봇 시뮬레이션 시작

        System.out.println(count);  // 청소한 칸의 수 출력
    }
}

 

 

 

● 코드 작성 순서

단계	설명
1	dfs() 함수부터 구현 (전체 로직 흐름)
2	방향 배열 선언 (dx, dy)
3	전역 변수 선언 (map, cleaned, count 등)
4	main() 입력 처리 및 호출 흐름 작성
5	조건 체크, 디버깅, 범위 보강

 

 

 

 

 

예제 (N=3, M=3) 기준으로 로봇의 상태 변화 를 단계별로 시각화

 

Start (1,1,↑)
로봇이 (1,1) 위치에서 북쪽(↑) 을 보고 시작합니다.

청소 (1,1)
현재 위치가 아직 청소되지 않았으므로 청소 수행 → count++

회전 → ←
왼쪽(서쪽)으로 회전 시도

벽 → 회전
서쪽이 벽이라 이동 불가 → 다시 회전

회전 → ↓
다음 왼쪽(남쪽) 확인

빈칸 → 이동 (2,1)
남쪽은 청소되지 않은 빈칸 → 그 방향으로 이동

청소 (2,1)
새 위치 (2,1)에서 청소 수행

4방향 실패 → 후진 (1,1)
이후 네 방향 모두 청소 불가 → 후진 시도

후진 실패 → 종료
후진 방향도 벽이면 작동 종료

 

 

 

 

5)  리뷰

처음 이 문제를 봤을 때는 시뮬레이션 문제라는 건 알겠는데, 어떤 메서드부터 작성해야 할지 어려웠고, 
특히 회전이나 후진 같은 조건 흐름을 코드로 옮기는 게 꽤 어려웠습니다.
어떤 조건이 있어야할지 하나씩 메모하다보니 필요한 코드가 무엇인지 파악할 수 있었습니다.
그래서 다른 분들의 블로그 풀이를 참고해 흐름을 정리한 뒤, dfs() 메서드부터 먼저 구현해 나가는 방식으로 풀었습니다.