[백준] 14503번 : 로봇 청소기 - JAVA [자바]

https://www.acmicpc.net/problem/14503

---

📝 문제 설명

방의 크기 N x M과 로봇 청소기가 있는 좌표 (r, c)가 주어지고 바라보는 방향 d가 주어진다. 해당 칸에 0이 적혀 있으면 청소가 되지 않은 빈칸이고 1이 적혀 있으면 벽이 있는 것이다. 로봇 청소기가 청소하는 영역의 개수를 출력하면 된다.

✨ 제출 코드

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

public class Main{
    static int N;
    static int M;
    static int r,c,d;

    static int [][] graph;
    static boolean [][] visited;

    static int [] dx = {-1,0,1,0}; //북동남서
    static int [] dy = {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());

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

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

        graph = new int [N][M];
        visited = new boolean[N][M];

        for(int i = 0; i < N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < M; j++){
                graph[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int result = clean();
        System.out.println(result);
        
    }

    public static int clean(){
        int answer = 0;

        while(true){
            //청소하기
            if(!visited[r][c]){
                visited[r][c] = true;
                answer += 1;
            }

            boolean cleanOrWallAround = true;

            for(int i = 0; i < 4; i++){
                int nd = (d + 3) % 4; //반시계방향 회전
                int nx = r + dx[nd];
                int ny = c + dy[nd];

                if(nx>=0 && nx<N && ny>=0 && ny<M && graph[nx][ny] == 0 && !visited[nx][ny]){
                    r = nx;
                    c = ny;
                    d = nd;
                    cleanOrWallAround = false;
                    break;
                }

                d = nd;

            }

            if(cleanOrWallAround){
                int back = (d+2) % 4; //후진하기
                int bx = r + dx[back];
                int by = c + dy[back];

                if(bx>=0 && bx<N && by>=0 && by<M && graph[bx][by] == 0){ //후진
                    r = bx;
                    c = by;
                }else{ //후진할 수 없으면 중지
                    break;
                }
            }
        }
        return answer;
    }
}

 

✌️ 코드 설명

먼저 방향에 대해서 먼저 보겠다.

// 북(0), 동(1), 남(2), 서(3)
int[] dx = {-1, 0, 1, 0};
int[] dy = {0, 1, 0, -1};

 

문제에서 d가 0인경우 북쪽, 1인 경우 동쪽, 2인 경우 남쪽, 3인 경우 서쪽이라했기 때문에 위처럼 설정해 주었다.

그리고 main함수에서 입력받을 것들을 다 입력받고 clean() 함수부터 살펴보겠다.

 

먼저 로봇 청소기는 (r, c)부터 시작하기 때문에 이 (r, c)에서 청소가 안되어있으면 청소를 진행해 준다. 코드에서는 boolean값을 true로 바꿔주었다. 그리고 청소 영역의 개수를 +1 해주었다. 

그 후 dx, dy를 이용해 다음 칸을 청소할 거다. 먼저 반시계 방향으로 회전하기 위해서 (d+3) % 4를 해주었다.

 

🔄 반시계 방향 회전

                               d                                      (d+3) % 4                                                     의미

0 (북)

3

서쪽(왼쪽)

1 (동)

0

북쪽(왼쪽)

2 (남)

1

동쪽(왼쪽)

 

3 (서)

2

남쪽(왼쪽)

 

🔙 후진(backward)

                                       d                                                  (d+2) % 4                                               의미

0 (북)	2	남쪽
1 (동)	3	서쪽
2 (남)	0	북쪽
3 (서)	1	동쪽

 

 

반시계 회전	(d + 3) % 4	현재 방향의 왼쪽
후진 (뒤로 가기)	(d + 2) % 4	현재 방향의 반대편

 

(d+3) % 4로 반시계 90`방향을 구하고 다음 nx, ny를 현재 좌표 r, c에 dx [nd], dy [nd]를 더해 다음 좌표를 구한다.

이 좌표가 청소가 가능한지를 살펴보고 가능하면 좌표 값을 바꿔주고 cleanOrWallAround = false;로 셋 해준다.

 

cleanOrWallAround = false는 4방향을 돌면서 청소할 수 있는 칸이 한 칸이라도 있다는 뜻이고

cleanOrWallAround = true는 4방향 모두 없는 것이다.

 

청소가능한 칸을 찾지 못했더라도 d = nd를 통해 방향은 바꿔준다.

 

그럼 이제 청소가능한 칸이 없는 경우를 보자. 해당 칸에서 후진할 수 있으며 한 칸 후진하고 청소를 하고 후진이 불가능하면 자동을 멈추면 된다.

 

위에서 구한 (d+2) % 4를 이용해 후진 방향을 구하고 이를 이용해 bx, by 즉 다음 후진했을 때의 칸을 구한다.

이 칸이 청소가 가능하면 그 칸으로 이동해 청소를 진행하고 아니면 break를 이용해 작동을 중지시킨다.