[BOJ/Java] 14503. 로봇 청소기

[BOJ/Java] 14503. 로봇 청소기

14503번: 로봇 청소기

---

문제 해석

본 문제는 로봇 청소기가 주어진 지도에서 청소 작업을 수행하는 과정을 시뮬레이션하는 것이다. 로봇 청소기는 초기 위치와 방향이 주어지며, 특정 규칙에 따라 움직이면서 공간을 청소한다. 로봇의 작동 규칙은 다음과 같다:

 

1. 현재 위치를 청소한다.
2. 현재 방향 기준 왼쪽 방향부터 차례로 탐색을 시도한다.
3. 왼쪽 방향에 청소하지 않은 공간이 존재하면, 그 방향으로 회전한 후 전진하고 1번으로 돌아간다.
4. 네 방향 모두 이미 청소되었거나 벽인 경우, 바라보는 방향을 유지한 채로 한 칸 후진 후 2번을 반복한다.
5. 후진할 수 없는 상황이면 작업을 종료한다.

목표는 로봇 청소기가 청소하는 칸의 수를 출력하는 것이다.

풀이 과정

제출된 코드는 DFS를 이용하여 로봇 청소기의 청소 프로세스를 구현한다. 로봇은 시작 위치에서부터 청소를 시작하며, 왼쪽 방향부터 청소 가능 여부를 확인하고 청소하거나 이동한다. 모든 방향이 막힌 경우에는 후진을 시도하고, 후진도 불가능할 때는 청소를 종료한다.

 

1. 방문 배열(visited): 각 위치의 청소 여부를 체크한다.
2. 청소 영역 카운트(ans): 청소하는 구역의 수를 계산한다. 초기 위치에서 청소를 시작하므로 1로 시작한다.
3. 방향 제어(direction): 로봇의 이동 방향을 제어하는 배열이며, 북, 동, 남, 서를 나타낸다.

코드

package edu.ssafy.im.BOJ.Gold.G5.No14503;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
    private int n, m; // 방의 세로(n)와 가로(m) 크기
    private int[][] map; // 방의 구조를 저장하는 2차원 배열
    private static final int[][] direction = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // 로봇의 이동 방향(북, 동, 남, 서)
    private boolean[][] visited; // 각 위치의 청소 여부를 저장하는 배열
    private int ans = 1; // 청소한 칸의 수, 시작 위치를 청소하므로 1로 초기화

    public static void main(String[] args) throws IOException {
        new Main().io();
    }

    private void io() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        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()); // 로봇의 초기 방향

        map = new int[n][m];
        visited = new boolean[n][m];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                map[i][j] = Integer.parseInt(st.nextToken()); // 방의 구조 입력(0: 빈 칸, 1: 벽)
            }
        }

        dfs(r, c, d); // 청소 시작

        sb.append(ans); // 청소한 칸의 수 출력
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    private void dfs(int r, int c, int d) {
        visited[r][c] = true; // 현재 위치 청소

        for (int i = 0; i < 4; i++) {
            d = (d + 3) % 4; // 현재 방향 기준으로 왼쪽 방향
            int nr = r + direction[d][0]; // 새로운 행 위치
            int nc = c + direction[d][1]; // 새로운 열 위치

            if (!(nr < 0 || nc < 0 || nr >= n || nc >= m || map[nr][nc] == 1 || visited[nr][nc])) {
                ans++; // 청소 가능한 경우 청소 영역 추가
                dfs(nr, nc, d); // 새 위치에서 청소 계속
                return;
            }
        }

        // 후진
        int nr = r - direction[d][0];
        int nc = c - direction[d][1];
        if (!(nr < 0 || nc < 0 || nr >= n || nc >= m || map[nr][nc] == 1)) {
            dfs(nr, nc, d); // 후진 위치에서 청소 계속
        }
    }
}

시간 복잡도 분석

이 알고리즘의 시간 복잡도는 O(N*M)이다. 로봇은 각 위치에서 최대 한 번씩 방문하며, 주어진 규칙에 따라 청소와 이동을 수행한다.

느낀점

로봇 청소기 문제를 통해 시뮬레이션과 DFS를 결합하여 복잡한 작동 규칙을 구현하는 방법을 학습할 수 있었다. 문제의 규칙을 코드로 옮기는 과정에서 방향 제어와 조건 분기 처리의 중요성을 깊이 이해하게 되었다.