[백준/JAVA] 14503번: 로봇 청소기

🔺 문제

14503번: 로봇 청소기

 

 

🧩  해결 아이디어

• 구현 & 시뮬레이션

1. 현재 칸의 주변 4칸 中 청소 안 된 빈 칸이 있는 경우, 반시계로 90도 회전하면서 주변을 청소할 수 있는지 확인한다.

   - 청소 안 된 곳이 있으면, cnt + 1하고 현재 좌표에서 dfs를 수행한다.

for(int i = 0 ; i < 4 ; i++) {
    dir = (dir + 3) % 4;	// 반시계로 90도 회전

    int nx = x + dx[dir];
    int ny = y + dy[dir];

    // 청소 안 된 곳 있으면, cnt++ & dfs
    if(inRange(nx, ny) && map[nx][ny] == 0) {
        cnt++;
        dfs(nx, ny);

        return; // ⭐ 여기서 종료 안 하면, 다른 곳 청소하러 갈 수도               
    }
}

 

 

2. 현재 칸의 주변 4칸 中 청소 안 된 빈 칸이 없는 경우 (= 주변이 모두 청소되어 있거나 벽인 경우),

한 칸 후진하고 그 위치에서 dfs를 수행한다.

int back = (dir + 2) % 4;   // 반대 방향
int bx = x + dx[back];
int by = y + dy[back];

if(inRange(bx, by) && map[bx][by] != 1) {
    dfs(bx, by);
}

 

 

💥 유의사항

- 청소한 칸 수는 1부터 시작한다. (시작 지점은 항상 청소 안 되어있다고 가정하므로)

- dx/dy 배열 순서를 "북 동 남 서" 순으로 저장해둬야 한다.

- 후진 시, x -= dx[dir] , y -= dy[dir]이 아니라, 반대 방향으로 이동해야 한다.

(예를 들어 현재 방향이 북쪽을 보고 있다면 남쪽으로 이동)

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] dx = {-1, 0, 1, 0};   // 북 동 남 서
    static int[] dy = {0, 1, 0, -1};
    
    static int N, M;    // 방 크기
    static int r, c;    // 로봇 청소기 위치
    static int dir;     // 바라보는 방향
    static int cnt = 1; // 청소한 칸 수 (시작 지점 때문에 1에서 시작)
    
    static int[][] map;
    
    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());
        
        String[] str = br.readLine().split(" ");
        r = Integer.parseInt(str[0]);
        c = Integer.parseInt(str[1]);
        dir = Integer.parseInt(str[2]);
        
        map = new int[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());
            }
        }
 
        dfs(r, c);
        
        System.out.println(cnt);
    }
    
    private static void dfs(int x, int y) {
        // 1. 현재 칸 청소
        map[x][y] = -1;
 
        // 2. 현재 칸 주변 4칸 中 청소 안 된 빈 칸 있는 경우,
        // 왼쪽 방향부터 차례대로 탐색 진행
        for(int i = 0 ; i < 4 ; i++) {
            dir = (dir + 3) % 4; // ⭐ 반시계로 90도 회전
            
            int nx = x + dx[dir];
            int ny = y + dy[dir];
            
            // 청소 안 된 곳 있으면, cnt++ & dfs
            if(inRange(nx, ny) && map[nx][ny] == 0) {
                cnt++;
                dfs(nx, ny);
                
                return; // ⭐ 여기서 종료 안 하면, 다른 곳 청소하러 갈 수도               
            }
        }
        
        // 2. 네 방향 모두 청소가 이미 되어있거나 벽인 경우,
        // 바라보는 방향 유지한 채 반대로 한 칸 후진
        int back = (dir + 2) % 4;   // ⭐ 반대 방향
        int bx = x + dx[back];
        int by = y + dy[back];
        
        if(inRange(bx, by) && map[bx][by] != 1) {
            dfs(bx, by);
        }
    }
    
    private static boolean inRange(int x, int y) {
        return (0 <= x && x < N && 0 <= y && y < M);
    }
}
 

 

 

---

🔺 다른 풀이들

- 약간 내가 풀려고 했던 방식이랑 비슷하심!!!!

[백준] 14503 - 로봇 청소기 (java)

 

---

💬 느낀 점

생각보다 코드가 간단해서 놀랐다.

크게 어려운 문제가 아닌 것 같은데 끝까지 마무리가 잘 안 된다ㅠ

복습해서 빠르게 풀 수 있게 해야지ㅠ

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

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

 

[백준] 14503번 - "로봇 청소기" (Java)