본문 바로가기
Algorithm/BaekJoon

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

v무지렁이v 2021. 9. 25. 16:12

Baekjoon 14503 - 로봇 청소기 (클릭 시 이동)

문제

로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오.

로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북중 하나이다. 지도의 각 칸은 (r, c)로 나타낼 수 있고, r은 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로 부터 떨어진 칸의 개수이다.

로봇 청소기는 다음과 같이 작동한다.

  1. 현재 위치를 청소한다.
  2. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향부터 차례대로 인접한 칸을 탐색한다.
    1. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.
    2. 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.
    3. 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.
    4. 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.

로봇 청소기는 이미 청소되어있는 칸을 또 청소하지 않으며, 벽을 통과할 수 없다.


시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 31371 16887 11055 52.784%

입력

첫째 줄에 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 50)

둘째 줄에 로봇 청소기가 있는 칸의 좌표 (r, c)와 바라보는 방향 d가 주어진다. d가 0인 경우에는 북쪽을, 1인 경우에는 동쪽을, 2인 경우에는 남쪽을, 3인 경우에는 서쪽을 바라보고 있는 것이다.

셋째 줄부터 N개의 줄에 장소의 상태가 북쪽부터 남쪽 순서대로, 각 줄은 서쪽부터 동쪽 순서대로 주어진다. 빈 칸은 0, 벽은 1로 주어진다. 지도의 첫 행, 마지막 행, 첫 열, 마지막 열에 있는 모든 칸은 벽이다.

로봇 청소기가 있는 칸의 상태는 항상 빈 칸이다.


출력

로봇 청소기가 청소하는 칸의 개수를 출력한다.


풀이

시키는대로 구현하면 되는 문제이지만 로직에 대한 분석이 조금 필요했다.

2번 과정만 조금 살펴봤을 때

2 - 1. 왼쪽 방향에 청소하지 않은 공간 존재 -> 회전 후 1칸 전진 후 count++


2 - 2. 왼쪽 방향에 청소할 공간이 없다면 그 방향으로 회전하고 2번과정을 처음부터 수행.

이 말의 의미는 4방향을 탐색하는데 청소할 공간이 있으면 그 공간을 청소할 수 있도록 2-1로 돌아가라는 말과 같다. for문을 통해 4방향을 탐색을 하게 될텐데

  1. 왼쪽 방향을 확인한다.
  2. 청소할 수 없는 공간이라면 그 방향으로 회전시켜준다
  3. 청소할 수 있는 공간이라면 회전시키지 않고 2-1로 돌아간다.(2-1에 회전하는 로직이 포함되기 때문)

2 - 3. 네 방향이 모두 청소되어 있거나 벽인 경우 바라보던 방향을 유지한 채로 (방향을 바꾸지 않고) 한칸 후진하고 2-1부터 다시 수행한다.

네 방향이 모두 청소되어 있거나 벽인 경우 -> 네방향 모두 청소할 수 없는 경우임을 의미한다.

청소할 수 있으면 2-2에서 이미 2-1로 되돌아 갔을 것이므로 고려할 필요가 없고 후진을 진행하고 2-1로 돌아간다.


2 - 4. 네 방향 모두 청소가 이미 되어 있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없을 경우 종료.

마찬가지로 청소할 수 있는지 없는지는 2-2를 진행하며 청소 할 수 있으면 2-3에도 도달하지 못한다.

뒤쪽 방향으로 후진할 수 있는 상태이면 2-3에서 2-1로 되돌아가기 때문에 2-4에 도달하지 못한다.


모든 과정을 boolean타입으로 선언하여 다음 단계로 넘어갈지 말지를 결정하고

2-3에서 다음단계로 넘어가게 된다면 종료하게끔 구현한다.


과정


boolean형 visited 배열을 통해 이미 청소했는지 안했는지 구분을 해 주었다.

visited + (map == 0) 이면 청소할 수 있는 공간

map== 0이면 이미 청소한 공간이라는 것을 짚고 넘어가면 코드를 조금 이해하기 수월하다.


또한, 0 : 북쪽, 1 : 동쪽, 2 : 남쪽, 3: 서쪽으로 방향이 명시가 되어 있는데, 왼쪽으로 회전하려면 -1을 해주어야 한다.

이는 북쪽인 경우에 -1을 해주면 인덱스를 벗어나므로 배열의 크기만큼 더해준 후 나머지를 구해주면 된다.

(distance -1 +4) % 4 == (distance + 3 ) %4 : 왼쪽으로 회전

(distance+2) % 4 : 후진

2-1 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행
static boolean move1() {
    int direction = (d + 3) % 4;    // 왼쪽방향 지정
    int nr = curr.r + deltas[direction][0];
    int nc = curr.c + deltas[direction][1];

    if (isIn(nr, nc) && map[nr][nc] == 0 && !visited[nr][nc]) { // 탐색 수행
        visited[nr][nc] = true;    // 방문처리
        curr.r = nr;    // 왼쪽 위치를 현재위치로 바꿔준다.
        curr.c = nc;
        d = direction;    // 방향도 바꿔준다.
        return false;    // 1로 되돌아가야 하므로 다음 과정을 진행하지 않는다.
    }
    return true;    // 만약 청소할 수 없다면 다음 과정으로 넘어간다.
}

2-2 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.

위의 과정에서 true를 반환했다면 회전한 후 다시 2-1을 수행하게 만든다.

왼쪽을 확인했을 때 청소할 공간이 없고

거기서 또 왼쪽으로 회전했을 때 청소할 공간이 있다면 2-1로 돌아가게 되는데,

2-1에서는 왼쪽으로 한번만 회전하므로 청소할 수 있으면 그 전 위치에서 되돌아가야 한다.


따라서, 4방향을 모두 탐색하며 그 전 위치를 현재 방향으로 지정해주고

발견하면 현재방향으로 지정하기 전에 false를 리턴한다.

모두 탐색하면(청소할 곳이 없다면) 4번 왼쪽으로 회전했기 때문에 원래위치로 되돌아오고 다음 과정으로 넘어갈 수 있게 true를 리턴한다.

static boolean move2() {
    int direction = d;
    int r = curr.r;
    int c = curr.c;
    for (int i = 0; i < 4; i++) {
        direction = (direction + 3) % 4;    // 다음 방향 지정
        int nr = r + deltas[direction][0];
        int nc = c + deltas[direction][1];
        if (isIn(nr, nc) && map[nr][nc] == 0 && !visited[nr][nc]) { // 탐색.
            return false;    //청소할 곳이 있으면 false를 리턴해 다음과정으로 넘어가지 못함.
        }
        d = direction;// 청소할 곳이 없으면 회전.
    }
    return true; // 4방향 모두 청소를 못하면 다음과정 진행.
}

2-3 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.

후진하는 로직만 구현한다.

static boolean move3() {
    int direction = (d + 2) % 4; // 후진할 때의 방향
    int nr = curr.r + deltas[direction][0];
    int nc = curr.c + deltas[direction][1];
    if (isIn(nr, nc) && map[nr][nc] == 0) {    // 벽이 아니고 배열을 벗어나지 않으면 후진
        curr.r = nr;
        curr.c = nc;
        return false;    // 후진하면 다시 2-1을 수행해야하므로 되돌아간다.
    }
    return true;    // 후진할 수 없는 경우 다음과정 진행
}
2-4 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.

위의 과정에서 true를 리턴하면 후진할 수 없는 경우이므로 작동을 멈추고 결과를 출력하면 된다.

최종 소스코드

package BJ_Practice;

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

public class BJ_G5_14503 {
    static int N, M;
    static RC curr = new RC(0, 0);
    static int d;
    static int[][] map;
    static boolean[][] visited;
    static int count = 0;
    static int[][] deltas = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };
    static StringTokenizer st;

    static class RC {
        int r, c;

        public RC(int r, int c) {
            super();
            this.r = r;
            this.c = c;
        }

        @Override
        public String toString() {
            return "RC [r=" + r + ", c=" + c + "]";
        }

    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

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

        st = new StringTokenizer(br.readLine());
        curr.r = Integer.parseInt(st.nextToken());
        curr.c = Integer.parseInt(st.nextToken());
        d = Integer.parseInt(st.nextToken());

        map = new int[N][M];
        visited = new boolean[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());
            }
        }
        visited[curr.r][curr.c] = true;

        while (true) {
            count++;    // 1
            while (move1()) {    // 2-1
                if (move2()) {    // 2-2
                    if (move3()) {    // 2-3
                        System.out.println(count); // 2-4
                        return;
                    }
                }
            }
        }
    }

    static boolean move1() {
        int direction = (d + 3) % 4;
        int nr = curr.r + deltas[direction][0];
        int nc = curr.c + deltas[direction][1];

        if (isIn(nr, nc) && map[nr][nc] == 0 && !visited[nr][nc]) {
            visited[nr][nc] = true;
            curr.r = nr;
            curr.c = nc;
            d = direction;
            return false;
        }
        return true;
    }

    static boolean move2() {
        int direction = d;
        int r = curr.r;
        int c = curr.c;
        for (int i = 0; i < 4; i++) {
            direction = (direction + 3) % 4;
            int nr = r + deltas[direction][0];
            int nc = c + deltas[direction][1];
            if (isIn(nr, nc) && map[nr][nc] == 0 && !visited[nr][nc]) {
                return false;
            }
            d = direction;

        }
        return true;
    }

    static boolean move3() {
        int direction = (d + 2) % 4;
        int nr = curr.r + deltas[direction][0];
        int nc = curr.c + deltas[direction][1];
        if (isIn(nr, nc) && map[nr][nc] == 0) {
            curr.r = nr;
            curr.c = nc;
            return false;
        }
        return true;
    }

    static boolean isIn(int r, int c) {
        return r >= 0 && r < N && c >= 0 && c < M;
    }
}




저작자표시

'Algorithm > BaekJoon' 카테고리의 다른 글

[백준] 3020번 - 개똥벌레 (java)  (0) 2021.10.02
[백준] 17143번 - 낚시왕 (java)  (0) 2021.10.02
[백준] 20058번 - 마법사 상어와 파이어스톰 (java)  (0) 2021.09.24
[백준] 17144번 - 미세먼지 안녕! (java)  (0) 2021.09.24
[백준] 1715번 - 카드 정렬하기 (java)  (0) 2021.09.22

'Algorithm/BaekJoon' Related Articles

티스토리툴바