[Algorithm] SW 기출문제 - 로봇 청소기(14503) 자바 풀이

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

 

이번 포스팅은 백준 SW 기출문제 - 로봇 청소기 자바 풀이를 진행하고자 합니다.

 

문제 출처: https://www.acmicpc.net/problem/14503

14503번: 로봇 청소기

 

 

1. 풀이 소스

 

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

import static java.lang.Integer.parseInt;

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

        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = parseInt(st.nextToken());
        int m = parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());

        int r = parseInt(st.nextToken());
        int c = parseInt(st.nextToken());
        int dir = parseInt(st.nextToken());

        RobotCleaner robot = new RobotCleaner(n, m);
        robot.setPoint(r, c, dir); // 처음 위치 및 방향 초기화

        for (int row = 0; row < n; row++) {
            st = new StringTokenizer(br.readLine());
            for (int col = 0; col < m; col++) {
                robot.setMap(row, col, parseInt(st.nextToken()));
            }
        }

        robot.run(); // 작동 시작

        System.out.println(robot.getCleanRoom());

    }
}

class RobotCleaner {

    static final int[] DR = {-1, 0, 1, 0};
    static final int[] DC = {0, -1, 0, 1};

    int n; // 행 개수
    int m; // 열 개수
    int[][] map; // 벽 혹은 이동 가능 영역 표시
    Point point; // 현재 위치
    int nowDir; // 북: 0, 동: 1, 남: 2,  서: 3
    int cleanRoom; // 총 청소한 구역
    boolean[][] visited; // 청소한 지역 (방문한다면 청소 해야 함)

    RobotCleaner (int n, int m) {
        this.n = n;
        this.m = m;
        map = new int[n][m];
        visited = new boolean[n][m];
    }

    void setPoint(int row, int col, int dir) {
        point = new Point(row, col);
        nowDir = dir;
    }

    void setMap(int row, int col, int value) {
        map[row][col] = value;
    }

    void run() {
        while(true) {

            int row = point.row; // point가 변경될 수 있으므로 임시 row
            int col = point.col; // 임시 col

            // 움직일 수 있고, 방문을 안했다면(청소가 가능하다면) <1>
            if (map[row][col] == 0 && !visited[row][col]) {
                cleanRoom++;
                visited[row][col] = true; // 방문 처리
            }

            boolean isNotCleanRoom = false; // 방문 가능한 곳 체크
            for (int i = 0; i < 4; i++) {
                int possibleR = row + DR[i];
                int possibleC = col + DC[i];

                if (!isValid(possibleR, possibleC)) continue; // 불가능한 곳

                isNotCleanRoom = true; // 청소할 곳 있음 <2> // isNotCleanRoom
                break;
            }

            if (isNotCleanRoom) {
                rotate(); // 회전하기

                //북: 0, 동: 1, 남: 2,  서: 3 이동하기
                if (nowDir == 0) row--; // 북 방향에서 한 칸 앞은 행 기준 --
                else if (nowDir == 1) col++; // 동 방향(오른쪽) 한 칸 앞
                else if (nowDir == 2) row++; // 남 기준 앞 row++
                else  col--; // 서 방향 기준 앞은 왼쪽

                if (!isValid(row, col)) continue;
                point.row = row;// 가능한 경우 업데이트
                point.col = col;
            }

            else { // 현재 칸의 주변 중 청소되지 않은 빈 칸이 없는 경우 <2>

                //북: 0, 동: 1, 남: 2,  서: 3
                if (nowDir == 0) row++; // 북 방향에서 한 칸 뒤는 남쪽으로
                else if (nowDir == 1) col--; // 동 방향(오른쪽) 한 칸 뒤 왼쪽
                else if (nowDir == 2) row--;
                else  col++;

                if (!isPossibleBackMove(row, col)) return; // 후진 불가능
                point.row = row; // 후진 가능하다면 위치 업데이트 후 while문 돌아가기
                point.col = col;
            }
        }
    }

    boolean isValid(int row, int col) { // 유효한 범위 && 이동 가능하고 && 청소하지 않음
        return row >= 0 && row < n && col >= 0 && col < m &&
                map[row][col] == 0 && !visited[row][col];
    }

    boolean isPossibleBackMove(int row, int col) { // 유효한 범위 && 후진하는 곳은 벽이 아니여야 함
        return row >= 0 && row < n && col >= 0 && col < m &&
                map[row][col] == 0;
    }

    void rotate() {
        switch (nowDir) { // 북: 0, 동: 1, 남: 2,  서: 3 
            case 0:
                nowDir = 3; // 북 -> 서
                break;
            case 1:
                nowDir = 0; // 동 -> 북
                break;
            case 2:
                nowDir = 1; // 남 -> 동
                break;
            case 3:
                nowDir = 2; // 서 -> 남
                break;
        }
    }

    int getCleanRoom() {
        return cleanRoom;
    }

    class Point {
        int row;
        int col;

        Point (int row, int col) {
            this.row = row;
            this.col = col;
        }
    }
}

 

 

2. 풀이 중점 사항

 

작동 사항 면밀하게 분석하기

 

해당 문제는 어떻게 코드를 작성해야 하는지 의사 코드를 명확하게 제시하고 있습니다. 따라서, 1 -> 2 or 3으로 반복적인 작업이 수행될 수 있도록 while 문 내부에서 적절한 분기 처리를 진행해야 합니다.

 

저는 2번 혹은 3번으로 분기가 처리되도록 하기 위해 isNotCleanRoom이라는 변수를 설정하였습니다.

총 4개의 상, 하, 좌, 우 에서 isValid() 메서드를 진행한 후, 만약 청소 가능한 구역이 하나라도 있다면 for문에서 빠져나와 isNotCleanRoom == true인 if 문으로 들어갑니다. 이후 회전을 진행하고 전진 여부를 판단하고 while문으로 돌아갑니다.

만약, 청소 가능한 구역이 없다면 isNotCleanRoom == false가 되어 후진 여부를 판단하여 while을 진행하거나 혹은 while을 종료합니다. 

 

그 외 부분은 자세한 주석으로 처리하였습니다.!

 

이상으로 로봇 청소기 자바 풀이를 마치도록 하겠습니다. 감사합니다.!!