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

백준 14503번 문제 - 로봇 청소기

14503번: 로봇 청소기

---

문제 분석

 

 

• 로봇청소기가 청소하는 영역의 개수 출력
  • 처음 지정받은 칸도 청소함
  • 주변 4칸 중 청소할 칸이 있음 : 90도로 반시계방향으로 돌아서 청소해야하면 청소 (아니면 계속 돌기)
  • 주변 4칸 중 청소할 칸이 없음 : 뒤에 벽이 없을 경우 뒤로 후진한다. 벽이 있을 경우 청소기를 멈춘다.

---

 

해결 키 포인트

 

• DFS 사용
• 처음 지정받은 칸도 청소함 : count 초기값 1
• 주변에 청소할 칸 확인은 90도 반시계방향 부터 : direction = (direction + 3) % 4;
• map 체크할 때 필자가 헷갈린 부분 : map[y][x] 인지 map[x][y]인지이다.
  map을 입력 받을 때 map[i][j]로 입력 받은 경우, map[y][x]임을 기억 !
• 닦을 곳이 없을 경우 direction을 바꾸면 안됨. 방향은 그대로되 후진하는 것이다 !
  • 후진 : int back = (direction + 2) % 4;

---

 

코드

 

import java.io.*;
import java.util.*;

public class Main {
    static int N, M, count = 1;
    static int map[][];
    static int dy[] = {-1, 0, 1, 0};  // 북동남서
    static int dx[] = {0,1,0,-1};

    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());
        map = new int[N][M];

        st = new StringTokenizer(br.readLine());
        int x = Integer.parseInt(st.nextToken());
        int y = Integer.parseInt(st.nextToken());
        int d = Integer.parseInt(st.nextToken()); // 방향 0북 , 1동, 2남, 3서

        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(x, y, d);
        System.out.println(count);
    }

    public static void dfs(int y, int x, int direction) {
        map[y][x] = -1;

        // 닦을 곳이 있어서 앞으로
        for (int i = 0; i < 4; i++) {
            direction = (direction + 3) % 4;

            int ny = y + dy[direction];
            int nx = x + dx[direction];
            if (nx >= 0 && ny >= 0 && nx < M && ny < N && map[ny][nx] == 0) {
                count++;
                dfs(ny, nx, direction);
                return;
            }
        }

        // 닦을 곳이 없어서 뒤로
        int back = (direction + 2) % 4;

        int by = y + dy[back];
        int bx = x + dx[back];
        if (bx >= 0 && by >= 0 && bx < M && by < N && map[by][bx] != 1) {
            dfs(by, bx, direction);
        }
    }
}