[백준] 14503번 : 로봇 청소기 - 자바[Java]

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

14503번: 로봇 청소기

풀이

문제에서 주어진 대로 로봇 청소기의 동작을 구현하면 된다.

로직

1. static 변수로 n, m, cnt, room, dr, dc를 선언한다.

cnt는 로봇 청소기가 청소하는 칸의 개수로 정답을 의미한다.

room은 청소하는 영역의 상태 정보를 저장하는 2차원 배열로, 아직 청소하지 않은 경우에는 0, 벽인 경우에는 1, 청소한 경우에는 2를 저장한다.

1차원 배열 dr과 dc는 방향 배열로 인덱스가 0인 경우에는 북쪽을, 1인 경우에는 동쪽을, 2인 경우에는 남쪽을, 3인 경우에는 서쪽을 바라보도록 한다.

2. n과 m, 로봇 청소기가 있는 칸의 좌표 (r, c)와 바라보는 방향 dir을 입력받고, 청소하는 영역의 상태를 입력받는다.

3. clean(r, c, dir)을 호출하여 로봇 청소기의 동작을 구현한다.

4. cnt를 출력한다.

 

void clean(int r, int c, int dir) : 로봇 청소기의 현재 위치가 (r, c)이면서 현재 방향이 dir일 때, 로봇 청소기의 동작을 구현한다.

    static void clean(int r, int c, int dir) {

        //현재 위치를 청소
        if (room[r][c] == 0) {
            cnt++;
            room[r][c] = 2;
        }

        int blocked = 0;

        int nr = r, nc = c, ndir = dir;

        while(true) {
            if (blocked == 4) break; //네 방향 모두 청소가 이미 되어있거나 벽인 경우

            ndir = (ndir + 3) % 4; //현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색

            //각각 다음 위치의 로봇 청소기의 좌표(nr, nc)
            nr = r + dr[ndir];
            nc = c + dc[ndir];

            if (nr >= 0 && nr < n && nc >= 0 && nc < m) {
                //아직 청소하지 않은 공간이 존재하는 경우 break
                if (room[nr][nc] == 0) {
                    break;
                }
                else blocked++;
            }
            else blocked++;
        }

        //아직 청소하지 않은 공간이 존재하는 경우이므로 바뀐 방향을 가지고 그 위치로 이동
        if (blocked < 4) {
            clean(nr, nc, ndir);
        }
        //네 방향 모두 청소가 이미 되어있거나 벽인 경우
        else {
            nr = r + dr[(dir+2) % 4];
            nc = c + dc[(dir+2) % 4];

            //후진할 수 있는 경우 바라보는 방향을 유지한 채로 한 칸 후진
            if (nr >= 0 && nr < n && nc >= 0 && nc < m && room[nr][nc] != 1) {
                clean(nr, nc, dir);
            }
        }

    }

1. 먼저 현재 위치가 아직 청소되지 않았다면 현재 위치를 청소한다. 이 때 청소한 위치는 2로 변경한다.

2. while문을 사용하여 현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다. 아직 청소하지 않은 공간이 존재하는 경우 반복문을 탈출하고, 그렇지 않으면 blocked에 1을 더한다. 이 때 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는 blocked는 4가 된다.

3. blocked가 4 미만이라면 아직 청소하지 않은 공간이 존재하는 경우이므로 clean(nr, nc, ndir)을 호출하여 바뀐 방향을 가지고 그 위치로 이동한다.

4. blocked가 4이상이라면 네 방향 모두 청소가 되어있거나 모두 벽인 경우이므로, 뒤쪽 방향이 벽이 아닌 경우(room[nr][nc] != 1)에는 clean(nr, nc, dir)을 호출하여 바라보는 방향을 유지한 채로 한 칸 후진을 한다. 

 

코드

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

public class Main {

    static int n, m;
    static int cnt = 0; //로봇 청소기가 청소하는 칸의 개수

    //청소하는 영역의 상태 정보, 아직 청소하지 않은 경우에는 0, 벽인 경우에는 1, 청소한 경우에는 2
    static int[][] room;

    //방향 배열, 0인 경우에는 북쪽을, 1인 경우에는 동쪽을, 2인 경우에는 남쪽을, 3인 경우에는 서쪽을 바라봄
    static int[] dr = {-1, 0, 1, 0};
    static int[] dc = {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());

        st = new StringTokenizer(br.readLine());
        int r = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());
        int dir = 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(r, c, dir);

        System.out.println(cnt);
    }

    static void clean(int r, int c, int dir) {

        //현재 위치를 청소
        if (room[r][c] == 0) {
            cnt++;
            room[r][c] = 2;
        }

        int blocked = 0;

        int nr = r, nc = c, ndir = dir;

        while(true) {
            if (blocked == 4) break; //네 방향 모두 청소가 이미 되어있거나 벽인 경우

            ndir = (ndir + 3) % 4; //현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색

            //각각 다음 위치의 로봇 청소기의 좌표(nr, nc)
            nr = r + dr[ndir];
            nc = c + dc[ndir];

            if (nr >= 0 && nr < n && nc >= 0 && nc < m) {
                //아직 청소하지 않은 공간이 존재하는 경우 break
                if (room[nr][nc] == 0) {
                    break;
                }
                else blocked++;
            }
            else blocked++;
        }

        //아직 청소하지 않은 공간이 존재하는 경우이므로 바뀐 방향을 가지고 그 위치로 이동
        if (blocked < 4) {
            clean(nr, nc, ndir);
        }
        //네 방향 모두 청소가 이미 되어있거나 벽인 경우
        else {
            nr = r + dr[(dir+2) % 4];
            nc = c + dc[(dir+2) % 4];

            //후진할 수 있는 경우 바라보는 방향을 유지한 채로 한 칸 후진
            if (nr >= 0 && nr < n && nc >= 0 && nc < m && room[nr][nc] != 1) {
                clean(nr, nc, dir);
            }
        }

    }

}

 

주의할 점
문제를 풀다가 막힌 부분이 있었다.
처음에 문제를 풀 때 현재 위치를 청소하면 벽과 같은 취급으로 하여 모두 1로 변경했는데, 이렇게 구현하니 "네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우"를 구현하는 부분에서 문제가 생겨 오답을 출력했다. 뒤쪽 방향이 벽인 경우에만 후진을 할 수 없는 거지 이미 청소한 구역은 후진이 가능하다. 그러므로 이미 청소한 구역은 2로 변경하고, "뒤쪽 방향이 벽"인지 판단하는 if문의 조건을 room[nr][nc] != 1로 수정하여 문제를 풀었다.

 

---

다른 풀이 2

• 현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행할 때, while문이 아닌 for문을 사용한다.
• for문을 통해 탐색을 진행하다가 아직 청소하지 않은 구간을 발견하면 바로 clean(nr, nc, ndir)을 호출하고 리턴한다.
• room을 탐색할 때 nr >= 0 && nr < n && nc >= 0 && nc < m 와 같이 인덱스 체크를 따로 하지 않아도 된다. 왜냐하면 문제의 입력에서 "지도의 첫 행, 마지막 행, 첫 열, 마지막 열에 있는 모든 칸은 벽이다."라고 나와있으므로 영역의 가장자리에서 탐색이 막혀서 인덱스 밖으로 탐색을 할 일이 없기 때문이다.

import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {

    static int n, m;
    static int cnt = 0; //로봇 청소기가 청소하는 칸의 개수

    //청소하는 영역의 상태 정보, 아직 청소하지 않은 경우에는 0, 벽인 경우에는 1, 청소한 경우에는 2
    static int[][] room;

    //방향 배열, 0인 경우에는 북쪽을, 1인 경우에는 동쪽을, 2인 경우에는 남쪽을, 3인 경우에는 서쪽을 바라봄
    static int[] dr = {-1, 0, 1, 0};
    static int[] dc = {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());

        st = new StringTokenizer(br.readLine());
        int r = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());
        int dir = 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(r, c, dir);

        System.out.println(cnt);
    }

    static void clean(int r, int c, int dir) {

        //현재 위치를 청소
        if (room[r][c] == 0) {
            cnt++;
            room[r][c] = 2;
        }

        int nr = r, nc = c, ndir = dir;

        for(int i = 0; i < 4; i++) {

            ndir = (ndir + 3) % 4; //현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색

            //각각 다음 위치의 로봇 청소기의 좌표(nr, nc)
            nr = r + dr[ndir];
            nc = c + dc[ndir];

            //아직 청소하지 않은 공간이 존재하는 경우
            if (room[nr][nc] == 0) {
                clean(nr, nc, ndir);
                return;
            }
        }

        //네 방향 모두 청소가 이미 되어있거나 벽인 경우
        ndir = (dir + 2) % 4;
        nr = r + dr[ndir];
        nc = c + dc[ndir];
        //후진할 수 있는 경우 바라보는 방향을 유지한 채로 한 칸 후진
        if (room[nr][nc] != 1) {
            clean(nr, nc, dir);
        }

    }

}

 

참고:

• https://velog.io/@hammii/%EB%B0%B1%EC%A4%80-14503-%EB%A1%9C%EB%B4%87-%EC%B2%AD%EC%86%8C%EA%B8%B0-java
• https://bbangson.tistory.com/m/55

---

위가 1번째 풀이(while문), 아래가 2번째 풀이(for문)