백준 14503번 : 로봇 청소기 java

이 문제는 주어진 조건에 맞게 코드를 만드는 문제입니다.

그림을 통해서 이 문제에 대한 설명을 드리도록 하겠습니다.

위의 그림과 같이 자료가 주어졌다고 가정해보도록 하겠습니다.

또한 로봇 청소기가 있는 위치는(1, 2)로 주어졌고, 방향은 2인 남쪽이 주어졌다고 하겠습니다.

이를 지도 위에 나타내 보겠습니다.

그럼 위의 그림과 같은 모양이 됩니다.

이때 문제의 1번 작업을 해줍니다.

청소한 위치는 빨간색으로 표시하겠습니다.

1번 작업을 하였으니 이제 2번 작업을 실행시켜 줍니다.

 로봇은 남쪽을 바라보고 있었으니 이 로봇의 왼쪽은 동쪽이 됩니다.

로봇의 동쪽에는 청소하지 않은 구역이 있고 벽이 아니니 이 방향으로 이동시켜줍니다.

위와 같은 그림이 됩니다.

1번 작업을 통해 현재 있는 칸을 청소해준 다음 2번 작업을 진행시킵니다.

이때 로봇은 동쪽을 바라보고 있으니 로봇이 바라보는 왼쪽은 북쪽이 됩니다.

로봇이 있는 칸의 북쪽은 벽이 있으니 이 칸으로는 진행할 수 없습니다.

따라서 로봇은 북쪽으로 바라보는 방향만 바꿉니다.

또한 2번 작업에서 1번으로 돌아가거나 후진하지 않고 4번을 회전만 한다면 1칸 후진한다는 조건이 있습니다.

이때 회전을 몇 번 했는지를 stop 변수에 넣어줍니다.

이 작업에서 회전을 1번 했으니 stop은 1이 됩니다.

이번엔 로봇이 북쪽을 바라보고 있습니다.

로봇이 바라보는 방향의 왼쪽은 서쪽이니 서쪽에 청소하지 않은 공간이 있는지 확인합니다.

로봇의 왼쪽은 이미 로봇이 청소를 하고 왔으니 갈 수 없습니다.

따라서 stop을 2로 바꿔주고 로봇을 서쪽을 바라보게 만들어줍니다.

이번에도 로봇이 서쪽을 보고 있지만 로봇이 바라보는 방향의 왼쪽인 남쪽에 벽이 있으므로 이동할 수 없습니다.

따라서 stop을 3으로 만들어주고 로봇이 남쪽을 바라보게 만들어줍니다.

이제 로봇이 남쪽을 바라보고 있습니다.

로봇이 바라보는 방향의 왼쪽은 동쪽입니다.

동쪽은 로봇이 청소하지 않았고 벽이 없으므로 동쪽으로 바라보는 방향을 바꾸고 이동해줍니다.

문제의 조건에서는 이동하지 않고 회전할 때을 연속으로 할 때만 stop이 4가 되면 후진한다고 하였습니다.

이번에 이동을 했기 때문에 stop을 0으로 바꾸어줍니다.

이제 문제의 조건에 맞게 회전하는 모습을 보여드리겠습니다.

이제 stop이 4가 되었습니다.

문제의 조건에서는 같은 자리에서 이동하지 않고 회전만 4번 했을 때 1칸 후진시키라고 하였습니다.

이 조건에 따라서 뒤로 1칸 이동해보도록 하겠습니다.

그럼 다음과 같은 그림이 됩니다.

하지만 이 자리에서도 회전을 계속 시켰을 때 이동할 수 있는 공간이 없습니다.

따라서 회전을 4번 시킨 후 다시 후진을 시켰을 때의 모습으로 넘어가도록 하겠습니다.

이제 문제의 조건에 따라서 다시 회전시키겠습니다.

이제 로봇이 바라보는 방향 왼쪽에 청소하지 않은 구역이 있으므로 이 칸으로 넘어가 줍니다.

바라보는 방향 왼쪽에 갈 수 있으니 이동해줍니다.

다시 회전시켜줍니다.

이제 이동시켜 줍니다.

위의 과정들을 반복하면 아래의 그림과 같이 됩니다.

이제 모든 칸들을 청소하였습니다.

하지만 문제의 종료 조건은 후진을 할 수 없을 때에 종료를 하기 때문에 이 문제가 종료되는 시점을 찾아가도록 하겠습니다.

이 로봇이 이제 청소할 수 있는 칸이 없기 때문에 계속 회전을 하게 됩니다.

회전을 계속하며 stop이 될 때마다 후진을 하고 후진을 할 수 없을 때 문제가 종료되게 됩니다.

계속 회전하며 후진하는 과정을 보여드리겠습니다.

위의 과정을 계속 반복해서 후진하게 됩니다.

이제 후진할 수 없으니 문제가 종료됩니다.

이 과정을 이제 코드로 구현해보도록 하겠습니다.

---

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

public class Main {
    static int N, M;
    static int count = 0;
    static int[][] map;
    static boolean[][] visited;

    static int[] dr = {-1, 0, 1, 0};
    static int[] dc = {0, 1, 0, -1};

    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());
        map = new int[N][M];
        visited = new boolean[N][M];

        st = new StringTokenizer(br.readLine());
        int r = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());
        int dir = Integer.parseInt(st.nextToken());

        for(int i = 0; i<N; i++){
            st = new StringTokenizer(br.readLine());

            for(int j = 0; j<M; j++)
                map[i][j] = Integer.parseInt(st.nextToken());
        }

        pathFind(r, c, dir);

        System.out.println(count);
    }

    static void pathFind(int r, int c, int dir){
        int nowR = r;
        int nowC = c;
        int nowDir = dir;

        int stop = 0;

        while(true){
            if(stop == 4){
                int backDir = nowDir-2<0 ? nowDir+2 : nowDir-2;
                int backR = nowR + dr[backDir];
                int backC = nowC + dc[backDir];

                if(map[backR][backC] == 1)
                    break;
                else{
                    nowR = backR;
                    nowC = backC;
                    stop = 0;
                }
            }

            if(!visited[nowR][nowC]){
                visited[nowR][nowC] = true;
                count++;
            }

            int nextDir = nowDir-1<0 ? nowDir+3 : nowDir-1;
            int nextR = nowR + dr[nextDir];
            int nextC = nowC + dc[nextDir];

            //왼쪽에 청소하지 않은 빈 공간이 있을 때
            if(!visited[nextR][nextC] && map[nextR][nextC] == 0){
                nowR = nextR;
                nowC = nextC;
                nowDir = nextDir;
                stop = 0;
            }
            else{
                nowDir = nextDir;
                stop++;
            }
        }
    }
}

이 문제에서는 북쪽이 0 동쪽이 1 남쪽이 2 서쪽이 3을 의미합니다.

따라서 dir에 이 정보를 담아서 dr과 dc를 이용하여 바라보는 방향의 왼쪽 칸은 nextR, nextC로 나타냈습니다.