[BOJ] 백준 14503 - 로봇청소기 (자바)

삼성 SW 역량테스트,,,,,,

17년 상반기 DS부문 1번문제 였다.

맨 처음에는 그냥 if, while, for 등의 떡칠로 문제를 풀게 되었다.

2번째 풀 때는 반복문으로 풀면 조금 더 쉽지 않을까? 싶어서 Queue를 이용해서 풀었는데

다음 x,y좌표 구하는 규칙은 쉽게 구할 수 있었지만 방향을 구하는 규칙을 찾는데 너무 많은 시간을 투자했다.

결국 맨 처음 조건문,반복문 떡칠이 시간이 훨씬 조금 걸렸다.... 아무튼 풀긴 풀었다.

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

 --> 현재 위치 청소

2. 현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다. 

 --> 위치는 제자리, 방향만 왼쪽으로 회전

  2-1. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.

    --> 왼쪽으로 회전한 방향의 앞이 청소되지 않았다면 한칸 전진한 후 1번으로 진행한다. (즉 앞의 칸 청소부터 다시 시작한다)

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

    --> 왼쪽으로 회전한 방향의 앞이 청소할 공간이 없다면, 다시 왼쪽으로 회전한다.

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

    --> 한바퀴를 다 돌았을 때 (네방향 모두 청소가 되어있을 때) 앞이 벽이라면, 뒤로 한칸 이동한다.

    --> 처음 바라보는 방향이 북쪽일 경우 탐색은 서쪽, 남쪽, 동쪽, 북쪽 순이 된다. 결국 마지막에 바라보는 방향은 북쪽이다. 그럴경우 남쪽으로 후진한다.

  2-4. 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.

     --> 말 그대로...

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

로봇청소기의 동작과정이다. 저 문제를 이해하는게 엄청 어렵다. 내가 설명을 잘 했는지도 잘 모르겠다.

문제만 잘 이해한다면 쉽게 풀 수 있는 문제이다. 풀이도 딱히 필요없다. 

풀이

풀이는 이동과정으로 대체 한다.

소스 - 1 (규칙 없이)

import java.io.FileInputStream;
import java.util.Arrays;
import java.util.Scanner;
 
public class Main {
    static int seo = 3;
    static int dong = 1;
    static int nam = 2;
    static int buk = 0;
 
    public static void main(String[] args) throws Exception {
 
        //Scanner sc = new Scanner(new FileInputStream("input.txt"));
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
 
        int r = sc.nextInt()+1;
        int c = sc.nextInt()+1;
        int d = sc.nextInt();
 
        int[][] arr = new int[N + 2][M + 2];
 
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                arr[i][j] = sc.nextInt();
            }
        }
        int cnt = 0;
        int result = 0;
        while (r > 0 && c > 0 && r <= N && c <= M) {
            arr[r][c] = -1;
            // System.out.println(r + " " + c + " " + d);
            // sc1.nextLine();
            if (cnt == 4) {
                if (d == dong) {
                    if (arr[r][c - 1] == 1) {
                        break;
                    }
                    c--;
 
                } else if (d == seo) {
                    if (arr[r][c + 1] == 1) {
                        break;
                    }
                    c++;
                }
 
                else if (d == nam) {
                    if (arr[r - 1][c] == 1) {
                        break;
                    }
                    r--;
                } else if (d == buk) {
                    if (arr[r + 1][c] == 1) {
                        break;
                    }
                    r++;
                }
                cnt = 0;
            }
 
            else {
                if (d == dong) {
                    if (arr[r - 1][c] == 0) {
                        cnt = 0;
                        r--;
                        result++;
                    } else {
                        cnt++;
                    }
                    d = buk;
 
                } else if (d == seo) {
                    if (arr[r + 1][c] == 0) {
                        cnt = 0;
 
                        r++;
                        result++;
                    } else {
                        cnt++;
                    }
                    d = nam;
 
                }
 
                else if (d == nam) {
                    if (arr[r][c + 1] == 0) {
                        cnt = 0;
 
                        c++;
                        result++;
                    } else {
                        cnt++;
                    }
                    d = dong;
 
                } else if (d == buk) {
                    if (arr[r][c - 1] == 0) {
                        cnt = 0;
 
                        c--;
                        result++;
                    } else {
                        cnt++;
                    }
                    d = seo;
 
                }
            }
        }
        result = 0;
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                //System.out.print(arr[i][j] + "\t");
                if (arr[i][j] == -1) {
                    result++;
                }
            }
            //System.out.println();
 
        }
        System.out.println(result);
    }
}

소스 - 2 (규칙으로)

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
 
public class Main {
 
    static int[] dx = { -1, 0, 1, 0 };
    static int[] dy = { 0, 1, 0, -1 };
    static int N;
    static int M;
    static int count = 0;
 
    public static void main(String[] args) throws Exception {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
 
        String[] str = br.readLine().split(" ");
 
        N = Integer.parseInt(str[0]);
        M = Integer.parseInt(str[1]);
        str = br.readLine().split(" ");
        int start_x = Integer.parseInt(str[0]);
        int start_y = Integer.parseInt(str[1]);
        int start_dir = Integer.parseInt(str[2]);
 
        int[][] arr = new int[N][M];
 
        for (int i = 0; i < N; i++) {
            str = br.readLine().split(" ");
            for (int j = 0; j < M; j++) {
                arr[i][j] = Integer.parseInt(str[j]);
            }
        }
        //--------------입력--------------
        
        Search(arr, start_x, start_y, start_dir);    //청소 실행 함수
        Check(arr);    //청소한 칸의 개수를 구함
        System.out.println(count);
    }
 
    public static void Search(int[][] arr, int start_x, int start_y, int start_dir) {
        Queue<Dot> q = new LinkedList<Dot>();
        arr[start_x][start_y] = 9;
        q.add(new Dot(start_x, start_y, start_dir));
        while (!q.isEmpty()) {
            Dot d = q.poll();
            int currentX = d.x;    //현재 x좌표
            int currentY = d.y;    //현재 y좌표
            int currentD = d.dir;    //현재 방향
            Boolean flags = false;    //4방향이 다 청소돼있거나 벽일 경우를 판단해줌.
            int nextX;
            int nextY;
            int nextD;
 
            for (int i = 0; i < 4; i++) {
                currentD = (currentD + 3) % 4;    //다음 이동할 방향
                nextX = currentX + (dx[currentD]);    //다음 이동할 X좌표
                nextY = currentY + (dy[currentD]);    //다음 이동할 Y좌표
 
                Dot nextDot = new Dot(nextX, nextY, currentD);
                if (nextX < 0 || nextY < 0 || nextX >= N || nextY >= M) {
                    continue;
                }
                //다음 이동할 위치가  청소되지 않은 곳이라면 간다.
                if (arr[nextX][nextY] == 0) {
                    q.add(nextDot);
                    arr[nextX][nextY] = 9;
                    flags = true;
                    break;
                }
            }
            //4방향다 청소됐거나 벽일 경우에는 후진해야한다.
            if (!flags) {
                nextD = (currentD + 2) % 4;
                nextX = currentX + dx[nextD];
                nextY = currentY + dy[nextD];
 
                //만약 후진할 곳이 벽이 아니라면, 이동 그렇지 않다면 종료한다.
                if (arr[nextX][nextY] != 1) {
                    arr[nextX][nextY] = 9;
                    q.add(new Dot(nextX, nextY, currentD));
                }
            }
        }
    }
 
    //청소한 칸의 개수를 구하는 함수
    public static void Check(int[][] arr) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (arr[i][j] == 9)
                    count++;
                //System.out.print(arr[i][j] + "\t");
            }
            //System.out.println();
        }
    }
}
 
class Dot {
    int x;
    int y;
    int dir;
 
    Dot(int x, int y, int dir) {
        this.x = x;
        this.y = y;
        this.dir = dir;
    }
}