[백준] 14503번 : 로봇 청소기

14503번: 로봇 청소기

---

[BFS]

BFS를 이용해서 풀었다. 일반적인 BFS와 다른 점은, 보통 BFS는 현재 정점에서 탐색할 수 있는 모든 정점을 Queue에 넣지만, 이 문제는 현재 정점에서 한 개의 정점만 큐에 넣을 수 있다. 큐에 들어갈 원소는 y좌표, x좌표 그리고 방향이다.

    static class Point{
        int y, x, dir;
        public Point(int yy, int xx, int d){
            y=yy;
            x=xx;
            dir = d;
        }
    }

현재 방향에 따라 다음 방향이 정해지고, 다음 방향이 정해져야 다음 좌표가 정해진다. 따라서 현재 방향은 필수적인 요소이다.

현재 방향이 1(동쪽)이라고 하자. 이때 왼쪽으로 회전하면 0(북쪽)을 가리킨다. 그럼 북쪽에서 좌측으로 회전하면? 서쪽이다. 서쪽은 3이므로 0 - 1 = 3이 되어야 한다. 따라서 if(nDir < 0) nDir = 3 처럼 조건문으로 변경해주어야 한다.

 

나는 주변에 방문할 정점이 있는지 탐색하기 전에 flag를 하나 준비했다. 만약 주변에 방문할 정점이 없다면 flag는 false를 가지게 되며, flag == false면 뒤로 한칸씩 후진한다. 이때 후진하다가 벽을 만나면 탐색은 종료된다.

 

뒤로 후진하는 방법은 간단하다. 현재 좌표에서 해당 방향으로 1칸씩 빼주면 된다.

# Code </>

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 class Point{
        int y, x, dir;
        public Point(int yy, int xx, int d){
            y=yy;
            x=xx;
            dir = d;
        }
    }
    static int r, c, cnt = 1;
    static int[] Y = {-1, 0, 1, 0}, X = {0, 1, 0, -1};
    static int[][] map = new int[51][51];
    static boolean[][] visit = new boolean[50][50];

    static void clean(Point start){
        Queue<Point> Q = new LinkedList<>();
        visit[start.y][start.x] = true;
        Q.add(new Point(start.y, start.x, start.dir));

        while(!Q.isEmpty()){
            Point p = Q.poll();
            int y = p.y;
            int x = p.x;
            int dir = p.dir;
            int nDir = dir;

            boolean isClean = false;
            for(int a=0; a<4; a++){ //주변의 정점 탐색
                nDir -= 1;
                if(nDir < 0) nDir = 3;

                int ny = y+Y[nDir];
                int nx = x+X[nDir];

                if(map[ny][nx] == 1 || visit[ny][nx]) continue;

                isClean = true;
                visit[ny][nx] = true;
                cnt++;

                Q.add(new Point(ny, nx, nDir));
                break;
            }

            if(!isClean) { //뒤로 후진
                int ny = y - Y[dir];
                int nx = x - X[dir];

                if(map[ny][nx] == 1)
                    break;

                Q.add(new Point(ny, nx, dir));
            }
        }
    }

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

        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());

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

        int y = Integer.parseInt(st.nextToken());
        int x = Integer.parseInt(st.nextToken());
        int dir = Integer.parseInt(st.nextToken());

        for(int i=0; i<r; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<c; j++)
                map[i][j] = Integer.parseInt(st.nextToken());
        }
        clean(new Point(y, x, dir));

        System.out.println(cnt);
    }
}