[문제 풀이] 백준 14503번 로봇 청소기 JAVA

문제

 

  문제접근 방법   

해당문제는 N과 M크기의 방이 존재하고 아래와 같이 동작할 때 로봇청소기가 작동을 시작한 후 작동을 멈출 때까지 청소하는 칸의 개수를 출력하는 프로그램을 작성하는 문제이다. 작동 방식은 다음과 같다.

 

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

문제를 보고 구현문제라는 것을 파악 후 조건을 계속해서 읽으면서 이해했다. 그 결과 총 4가지의 핵심 기능으로 나누어 

접근하기로 결정하였고 코드는 아래와 같다.

< 최종 코드 >

import java.util.*;

public class Main {
    public static boolean visited[][];
    public static int map[][];
    public static int cnt = 0;

    public static void main(String args[]) {
        Scanner s = new Scanner(System.in);
        int n = s.nextInt();
        int m = s.nextInt();

        visited = new boolean[n][m];
        map = new int[n][m];
        int y = s.nextInt();
        int x = s.nextInt();
        int d = s.nextInt();

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                map[i][j] = s.nextInt();
            }
        }

        dfs(y, x, d, 0);

        
        System.out.print(cnt);
    }

    public static void dfs(int y, int x, int d, int nsew) {
        if (map[y][x] == 1) return;

       if (!visited[y][x]) {
            visited[y][x] = true;
            map[y][x] = 2;
            cnt++;
        }

        int[] dx = {0, 1, 0, -1};
        int[] dy = {-1, 0, 1, 0};

        if (nsew == 4) {
            int backY = y;
            int backX = x;

            switch (d) {
                case 0: backY += 1; break; 
                case 1: backX -= 1; break; 
                case 2: backY -= 1; break; 
                case 3: backX += 1; break; 
            }

            if (backX < 0 || backY < 0 || backX >= map[0].length || backY >= map.length || map[backY][backX] == 1) return;

            y = backY;
            x = backX;
            nsew = 0;
        }

        int count = 0;

        while (count != 4) {
            d = (d + 3) % 4;
            int nx = x + dx[d];
            int ny = y + dy[d];

            if (nx >= 0 && ny >= 0 && nx < map[0].length && ny < map.length) {
                if (map[ny][nx] == 0 && !visited[ny][nx]) {
                    dfs(ny, nx, d, 0);
                    return;
                }
            }
            count++;
            nsew++;
        }

        dfs(y, x, d, nsew);
    }
}

최종 코드에서는 핵심로직 4가지만 소개하고 간단하게 넘어가도록 하겠다. 4가지는 아래와 같다.

 

• 현재 위치 청소하기
• 왼쪽 방향부터 회전하며 탐색
• 네 방향 다 안 되면 후진 (불가능하면 종료)
• DFS 재귀 호출로  반복

본인이 생각한 핵심로직은 이렇게 4가지이고 이렇게 코드를 작성하였다.

 

 

1. 현재 칸 청소하기

if (!visited [y][x]) { visited[y][x] = true; map [y][x] = 2; cnt++; }

 

• 로봇이 도착한 칸이 아직 청소되지 않았다면, 청소 처리 후 방문 체크(visited=true).
• 청소된 칸 수를 cnt에 누적.
• 문제 설명의 1번 규칙(현재 칸 청소) 구현 부분이다.

2. 왼쪽 방향 탐색 및 회전 처리

 

d = (d + 3) % 4; // 반시계 방향 회전
int nx = x + dx [d];
int ny = y + dy [d];...
if (map [ny][nx] == 0 &&! visited [ny][nx]) {
              dfs(ny, nx, d, 0);
               return; }

 

• 현재 방향 기준으로 왼쪽으로 회전한 뒤 앞칸을 확인.
• 앞칸이 빈칸(0)이고 아직 청소하지 않은 칸이면 그쪽으로 이동.
• 이동 시 DFS 재귀 호출로 다시 청소 시작.
• 문제 설명의 2번 규칙(왼쪽부터 차례로 탐색, 청소할 수 있으면 이동) 부분이다.

 

3. 네 방향 다 불가능할 때

if (nsew == 4) {
    int backY = y, backX = x;
    switch (d) {
        case 0: backY += 1; break;
        case 1: backX -= 1; break;
        case 2: backY -= 1; break;
       case 3: backX += 1; break; }
if (backX < 0 || backY < 0 || backX >= map [0]. length || backY >= map.length || map [backY][backX] == 1) return;

y = backY;
x = backX;
nsew = 0; }

 

• 네 방향 모두 청소할 수 없는 경우(nsew==4), 현재 방향은 유지한 채 뒤쪽 칸으로 후진.
• 뒤쪽이 벽이면 그대로 종료.
• 문제 설명의 3번 규칙(네 방향 모두 청소 불가 → 후진, 후진 불가 시 종료) 부분이다.

 

4. DFS 재귀 반복

dfs(ny, nx, d, 0); // 이동 가능한 경우
dfs(y, x, d, nsew); // 이동 불가능 → 회전 횟수 늘리고 반복

 

• 이동 가능하면 새로운 위치로 재귀 진입, 청소 이어가기.
• 이동 불가능하면 같은 자리에서 방향 회전만 하면서 다시 반복.
• 후진이나 종료 조건에 도달할 때까지 계속 재귀 호출이 이어진다

 

  마무리  

구현 문제들은 항상 아이디어는 쉽게 떠오르지만 그 과정이어렵운것 같다. 조금 더 문제를 분석하고 파악하는 능력을 키울 필요를 느끼었다.