[백준 - 14503] 로봇 청소기 - Java

문제 설명

 

14503번: 로봇 청소기

 

접근 방법

해당 문제는 BFS(너비 우선 탐색)를 통해 해결할 수 있었습니다.

 

로봇 청소기는 현재 장소에 대한 좌표값 뿐만 아니라, 현재 방향 정보를 가지고 있습니다. 이러한 정보를 바탕으로 별도의 로봇 청소기에 대한 구조체를 선언해주었습니다.

 

    static class Robot {
        int x;
        int y;
        int direction;
        int countOfCleaning;

        public Robot(int x, int y, int direction, int countOfCleaning) {
            this.x = x;
            this.y = y;
            this.direction = direction;
            this.countOfCleaning = countOfCleaning;
        }
    }

 

이때 문제에서 주어진 방향 정보는 북쪽이 0, 동쪽이 1, 남쪽이 2, 서쪽이 3을 나타내는데, 이를 기존 BFS에서 활용하던 dx와 dy 정보에 대한 인덱스를 활용한다면 각각의 방향별로 손 쉽게 나타낼 수 있게 됩니다.

 

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

 

이후 너비 우선 탐색 시 각각의 방향에 대한 노드 정보를 저장하기 위해 위 정보를 다음과 같이 활용해볼 수 있었습니다. 참고로 로봇의 방향은 현재 방향에서 왼쪽 방향부터 차례대로 탐색합니다. 현재 저장한 방향 정보는 '북, 동, 남 서' 순이므로 인덱스를 1씩 빼주어 방향을 바꿔주도록 합니다.

 

            // ... 

            for (int i = 1; i < 5; i++) {
                nd = robot.direction - i;
                if (nd < 0) {
                    nd += 4;
                }

                nx = robot.x + dx[nd];
                ny = robot.y + dy[nd];
                
                // ...
            }

 

이후 해당 방향으로 한 칸 전진했다고 가정했을 때 청소가 되어 있지 않다면(방문 처리 X, 벽 X) 바뀐 좌표 값과 방향 정보그리고 수정된 청소 횟수 정보와 함께 새로운 노드를 큐에 저장해줍니다. (방문 처리를 한 곳은 청소가 되었다고 가정해볼 수 있습니다.)

 

                if (room[nx][ny] == 0) {
                    visited[nx][ny] = true;
                    queue.add(new Robot(nx, ny, nd, robot.countOfCleaning + 1));
                    result = Math.max(result, robot.countOfCleaning + 1);
                }

 

하지만 네 개의 방향 모두 기존에 청소가 되있든 벽이 있었든 청소를 하지 못한 경우에는 다음과 같이 뒤로 후진시킨 다음(현재 방향은 유지) 이에 대한 정보를 바탕으로 새로운 노드를 큐에 저장해주도록 했습니다. 이제 앞선 작업들을 반복합니다. 참고로 뒤에 벽이 있는 경우는 해당 로봇은 아무 동작도 하지않는다고 했으므로 별도 처리가 필요 없습니다.

 

            if (robot.direction > 1) {
                nd = robot.direction - 2;
            } else {
                nd = robot.direction + 2;
            }

            nx = robot.x + dx[nd];
            ny = robot.y + dy[nd];

            if (room[nx][ny] != 1) {
                queue.add(new Robot(nx, ny, robot.direction, robot.countOfCleaning));
            }

 

전체 소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class Main {

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

    static class Robot {
        int x;
        int y;
        int direction;
        int countOfCleaning;

        public Robot(int x, int y, int direction, int countOfCleaning) {
            this.x = x;
            this.y = y;
            this.direction = direction;
            this.countOfCleaning = countOfCleaning;
        }
    }

    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()), c = Integer.parseInt(
            st.nextToken()), d = 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());
            }
        }

        boolean[][] visited = new boolean[n][m];

        operate(r, c, d, visited);

        System.out.println(result);
    }

    private static void operate(int x, int y, int d, boolean[][] visited) {

        Queue<Robot> queue = new LinkedList<>();
        queue.add(new Robot(x, y, d, 1));
        visited[x][y] = true;

        int nx, ny, nd;
        Loop: while (!queue.isEmpty()) {

            Robot robot = queue.poll();

            for (int i = 1; i < 5; i++) {
                nd = robot.direction - i;
                if (nd < 0) {
                    nd += 4;
                }

                nx = robot.x + dx[nd];
                ny = robot.y + dy[nd];

                if (visited[nx][ny]) {
                    continue;
                }

                if (room[nx][ny] == 0) {
                    visited[nx][ny] = true;
                    queue.add(new Robot(nx, ny, nd, robot.countOfCleaning + 1));
                    result = Math.max(result, robot.countOfCleaning + 1);
                    continue Loop;
                }
            }

            if (robot.direction > 1) {
                nd = robot.direction - 2;
            } else {
                nd = robot.direction + 2;
            }

            nx = robot.x + dx[nd];
            ny = robot.y + dy[nd];

            if (room[nx][ny] != 1) {
                queue.add(new Robot(nx, ny, robot.direction, robot.countOfCleaning));
            }
        }
    }
}

 

참고 자료

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