백준 14503 로봇 청소기

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

14503번: 로봇 청소기

 

로봇 청소기와 방의 상태가 주어졌을 때, 청소하는 영역의 개수 구하기

단순한 구현 문젠데 어디서 꼬인 건지 계속 답이 다르게 나와서 꽤 애를 먹었다.

 

 

---

방(room) 상태값

1: 벽

0: 청소X

-1: 청소O (청소를 하면 -1로 저장할 것)

 

---

로봇 청소기 작동 방식

1. 현재 칸이 0이면 청소

 

2-1. 현재 칸 주변 동서남북에 0이 있으면

 반시계 방향으로 90도 회전

 2-1-1. 바라보는 방향의 앞 칸이 0이면 전진 후 1번으로 돌아감

 2-1-2. 바라보는 방향의 앞 칸이 0이 아니면 다시 90도 회전

 

2-2. 현재 칸 주변 동서남북에 0이 없으면

 2-2-1. 뒷 칸이 -1이면 후진 후 1번으로 돌아감

 2-2-2. 뒷 칸이 -1이 아니면(벽이라는 뜻) 작동 종료

 

작동 방식을 살펴보면 1로 돌아가 다시 반복하고 있기 때문에 재귀로 풀 수 있다.

 

---

방향(dir)

0: 북

1: 동

2: 남

3: 서

 

반시계 방향으로 90도 회전 코드는 아래와 같이 생각해서 작성했다.

현재 로봇이

1. 서쪽(3)을 보고 있으면 남쪽(2)으로,

2. 남쪽(2)을 보고 있으면 서쪽(1)으로,

3. 서쪽(1)을 보고 있으면 북쪽(0)으로,

4. 북쪽(0)을 보고 있으면 서쪽(3)으로 회전

규칙을 찾아보면 1~3번은 모두 현재 방향(dir)에서 -1을 하면 90도 회전하는 것이다.

다만 4번은 0-1을 하면 -1이 되는데 이렇게 음수가 되면 그냥 직접 3을 반환하여 90도 회전한 방향(newDir)을 구했다.

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

    private static int[] dx = {-1, 0, 1, 0}; // 북, 동, 남, 서
    private static int[] dy = {0, 1, 0, -1};
    private static int[][] room;
    private static int count = 0;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        room = new int[N][M];

        int[] robot = new int[3];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < 3; i++) {
            robot[i] = Integer.parseInt(st.nextToken());
        }

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                room[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        start(robot[0], robot[1], robot[2]);
        System.out.println(count);

    }

    private static void start(int x, int y, int dir) { // x:row | y:col

        if (room[x][y] == 0) {
            room[x][y] = -1;
            count++;
        }

        if (isExistZero(x, y)) { // 동서남북으로 0이 있으면
            // 반시계방향으로 90도 회전하면서 0이 있는쪽 찾기
            int newDir = dir - 1;
            for (int i = 0; i < 4; i++) {
                if (newDir < 0) newDir = 3;
                int frontX = x + dx[newDir];
                int frontY = y + dy[newDir];
                if (room[frontX][frontY] == 0) { // 회전한 방향의 앞쪽에 0을 찾으면
                    start(frontX, frontY, newDir); // 전진 후 청소
                    break;
                } else { // 0을 못찾으면
                    newDir--; // 방향전환
                }
            }
        } else { // 동서남북으로 0이 없으면
            List<Integer> back = checkBack(x, y, dir);
            // 후진할 수 있으면(뒤의 좌표가 -1이면)
            if (room[back.get(0)][back.get(1)] == -1) start(back.get(0), back.get(1), dir);
                // 후진할 수 없으면 작동종료
            else return;
        }


    }

    // 후진할 좌표 구하기
    private static List<Integer> checkBack(int x, int y, int dir) {
        List<Integer> back = new ArrayList<>();
        int newDir;

        if (dir == 0) newDir = 2;
        else if (dir == 1) newDir = 3;
        else if (dir == 2) newDir = 0;
        else newDir = 1;

        back.add(0, x + dx[newDir]);
        back.add(1, y + dy[newDir]);

        return back;
    }

    // 동서남북으로 0이 있는지 확인
    private static boolean isExistZero(int x, int y) {
        for (int i = 0; i < 4; i++) {
            if (room[x + dx[i]][y + dy[i]] == 0) return true;
        }
        return false;
    }
}