[백준] 14503번 로봇 청소기

생각

로봇 청소기가 있다. 이 로봇 청소기는 아래와 같은 연산으로 청소를 진행한다. 청소를 하지 않은 지역은 '0' 벽은 '1'로 표신된다.

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

이 때 로봇 청소기가 청소하는 구역이 얼마나 되는지 구하여라.

비고 사항

삼성 SW 테스트 문제라고 한다.

처음 생각

정해진 조건에 맞게 구현을 해주었다. 청소기가 한 칸씩 이동을 하고 있으므로 Queue를 이용해서 청소기가 움직일 수 있는 상황이 아닐 때까지 진행해 주었다. 왼쪽을 본다는 의미가 바로 왼쪽인지 모르고 현 방향의 왼쪽 전부를 보았다가 수정하였다.

다음 생각

위에서 부터 구현을 하였더니 2-3) 에서 처리를 해줄 수 가 없었다. check 변수를 따로 하나 만들어 왼쪽으로 회전시 +1을 해주어 check가 3이 되면 한 바퀴를 돌아 갈 곳이 없는 것이므로 후진 처리해 주었다.

다다음 생각

구현은 다했고 예제도 맞았지만 제출하니 '틀렸습니다'가 나왔다. 무엇이 문제인지 찾던 중 습관에 의한 문제란 것을 발견하였다.

다다다음 생각

Switch문으로 조건 처리를 하여주었고 각 case에서 break를 통해 빠져나왔다. 이 부분이 잘 못된 것이였다. check가 3일 경우 후진을 하는 동작을 queue에 넣어주어 이 queue를 처리해 주어야하는데 continue가 아닌 평소대로 break문을 사용했기 때문에 check가 3이 아닐 경우에 동작하는 방식도 같이 queue에 넣어주고 있었다.

방안

1) break문을 continue로 고쳐 조건문을 빠져나오도록 하였다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
    static int[][] arr;
    static int n,m,r,c,d;
    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());
        arr = new int[n][m];
        st = new StringTokenizer(br.readLine());
        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
        d = Integer.parseInt(st.nextToken());
        for(int i=0;i<n;i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<m;j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        result = 0;
        solve();
        System.out.println(result);
    }
    
    // d -> 0은 위, 1 오른쪽, 2 아래, 3 왼쪽
    static int result;
    static int[][] dir = {{1,0},{0,1},{-1,0},{0,-1}};
    private static void solve() {
        Queue<Pair> queue = new LinkedList<>();
        queue.add(new Pair(r,c,d));
        boolean flag = false;
        int check = 0;
        while(!queue.isEmpty()) {
            Pair t = queue.poll();
            // 청소 구역인지 확인 -> 청소후 체크표시
            if(arr[t.x][t.y]==0) {
                result++;
                arr[t.x][t.y] = 3;
            }
            if(flag) break;
 
            // 해당 방향 기준 왼쪽 방향 체크
            if(checkLeft(t.x,t.y,t.dir)) {
                check = 0;
                // d -> 0은 위, 1 오른쪽, 2 아래, 3 왼쪽
                switch(d) {
                case 0:
                    queue.add(new Pair(t.x-1,t.y,d));
                    break;
                case 1:
                    queue.add(new Pair(t.x,t.y+1,d));
                    break;
                case 2:
                    queue.add(new Pair(t.x+1,t.y,d));
                    break;
                case 3:
                    queue.add(new Pair(t.x,t.y-1,d));
                    break;
                }
                // 회전 만 진행
            }else {
                // 4방향 다 안되는 경우
                if(check==3) {
                    check = 0;
                    // d -> 0은 위, 1 오른쪽, 2 아래, 3 왼쪽
                    switch(d) {
                    case 0:
                        if(arr[t.x+1][t.y]==1) flag = true;
                        queue.add(new Pair(t.x+1,t.y,d));
                        continue;
                    case 1:
                        if(arr[t.x][t.y-1]==1) flag = true;
                        queue.add(new Pair(t.x,t.y-1,d));
                        continue;
                    case 2:
                        if(arr[t.x-1][t.y]==1) flag = true;
                        queue.add(new Pair(t.x-1,t.y,d));
                        continue;
                    case 3:
                        if(arr[t.x][t.y+1]==1) flag = true;
                        queue.add(new Pair(t.x,t.y+1,d));
                        continue;
                    }
                }
                if(flag) break;
                check++;
                queue.add(new Pair(t.x,t.y,d));
 
            }
        }
        
    }
    
    private static boolean checkLeft(int x,int y,int dd) {
        switch(dd-1) {
        case 0: // 오른쪽을 보고있을 때
            d = 0;
            if(arr[x-1][y]!=0) return false;
            break;
        case 1: // 아래 보고있을 때
            d = 1;
            if(arr[x][y+1]!=0) return false;
            break;
        case 2: // 왼쪽 보고있을 때
            d = 2;
            if(arr[x+1][y]!=0) return false;
            break;
        case -1: // 위를 보고있을 때
            d = 3;
            if(arr[x][y-1]!=0) return false;
            break;
        }
        return true;
    }
    
    static class Pair{
        private int x,y,dir;
        
        public Pair(int x,int y,int dir) {
            this.x = x;
            this.y = y;
            this.dir = dir;
        }
    }
}