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

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

14503번: 로봇 청소기

 

[정답 코드]

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

public class Main {
    static int N, M;
    static int[][] room;
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1}; // 북, 동, 남, 서 순서
    static int count = 0;
    static boolean flag;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine(), " ");

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

        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());
            }
        }
        clean(robotX, robotY, robotHead);
        System.out.println(count);
    }

    static void clean(int x, int y, int head) {
        // 현재 위치가 더럽다면 청소
        if (room[x][y] == 0) {
            room[x][y] = 2; // 현재 위치 청소
            count++;
        }
        flag = false;
        for (int i = 0; i < 4; i++) {
            int nextHead = (head + 3) % 4; // 반시계 방향으로 90도 회전한 방향이 청소할 구역인지
            int nextX = x + dx[nextHead];
            int nextY = y + dy[nextHead];
            if (nextX >= 0 && nextY >= 0 && nextX < N && nextY < M) {
                if (room[nextX][nextY] == 0) {
                    clean(nextX, nextY, nextHead);
                    flag = true; // 청소할 구역이 있는 경우
                    break;
                }
            }
            head = (head + 3) % 4; // 반시계 90도 회전
        }


        if (!flag) { // 네 방향이 모두 청소된곳이거나 벽인 경우
            int nextHead = (head + 2) % 4; // 후진
            int nextX = x + dx[nextHead];
            int nextY = y + dy[nextHead];
            if (nextX >= 0 && nextY >= 0 && nextX < N && nextY < M) { // 후진할 공간이 있을 경우
                if (room[nextX][nextY] != 1) {
                    clean(nextX, nextY, head); // 후진
                }
            }
        }
    }
}

 

[설명]

이 문제는 4방탐색을 활용한 구현문제이다.

문제 설명이 이상해 이해하기 어렵지만 간단하게 정리하자면

1. 현재 위치를 청소한다.

2. 바라보는 방향에서 반시계 90도로 회전하면 청소할 수 있는지 탐색한다.

3 - 1. 청소할 수 있다면 전진한다. 그 후 1번으로 간다.

3 - 2. 청소할 수 없다면 후진한다.

4 - 1. 후진할 수 있다면 1번으로 간다.

4 - 2. 후진할 수 없다면 종료한다.

 

먼저 방의 로봇청소기의 위치와 방향을 clean 함수에 넣고 실행시킨다.

clean 함수는 로봇청소기의 위치가 청소해야할곳이라면 청소를 해 해당 위치를 임의의 숫자 2로 변경해준다.

그 후 4방탐색을 실시하는데 중요한 점은 4방탐색을 할 때 내가 바라보는 방향에서 반시계로 90도 씩 돌아가는 순서대로 탐색을 해야하는 것이다.

(head + 3) % 4 를 했을 경우 내가 바라보는 방향 head에서 반시계로 90도 돌게된다. 그리고 이를 4번할 경우 다시 원래방향을 바라보게 된다.

예를들어 head 가 0(북쪽) 일경우

(0 + 3) % 4 = 3(서쪽)

(3 + 3) % 4 = 2(남쪽)

(2 + 3) % 4 = 1(동쪽)

(1 + 3) % 4 = 0(북쪽)

이렇게 네 방향을 탐색했는데 모두 청소된 곳이거나 벽일경우 

(head + 2) % 4 를 하게되면 180도 뒤를 바라보게 된다.

만약 head 가 0(북쪽) 일경우

(0 + 2) % 4 = 2(남쪽)

이므로 후진을 할 수 있다.