[구현] 백준 14503: 로봇 청소기

오늘은 밀린 만큼 두 개를 복기하려 한다. 첫 번째 복기 대상 로봇 청소기이다.

14503번: 로봇 청소기 (acmicpc.net)

 

 

참고로, 북쪽의 왼쪽은 서쪽이다. 

 

왜 너무 당연한 이런 얘기를 썼냐면... 북동남서 순으로 0,1,2,3이 배정되어 있기 때문이다. 나는 북쪽의 왼쪽->0의 다음은 1 .. 이렇게 멋대로 생각하다가 꽤나 삽질을 했다...

 

한 칸 씩 네 방향을 서치할 수 있게 dr, dc 배열과, 중간에 청소를 안 한 부분을 발견하여 빠져나갈 때 재귀호출의 '방향' 인풋으로 사용하기 위해 directions 배열을 만들었다.

 

public class BOJ_14503 {
    static int N,M;
    static int[][] board;
    static int numCleaned = 0;
    //북->서->남->동->북->.... = 0->3->2->1 ...
    static int[] directions = {3,2,1,0,3,2,1,0};
    static int[] dr = {0,1,0,-1,0,1,0,-1};
    static int[] dc = {-1,0,1,0,-1,0,1,0};
    
    ..........

이 문제에서 헷갈리기 쉬운 점은, 방향 배정은 북동남서 순으로 되어 있는데 실제 순회해야 하는 방향은 북서남동순이라는 것이다. 

 

보통 이런 식으로 dx,dy 개념을 이용할때는 곧이곧대로 index를 이용해서 arr[y+dy[i]][x+dx[i]] ... 순으로 이용해 왔는데, 이 경우는 앞서 말한 대로 순회 방향과 방향 배정 방향이 반대이기 때문에 재귀함수 내에서 왼쪽 방향으로 한 바퀴를 돌고 호출하는 방식을 다음과 같이 구현했다.

 

        //왼쪽 방향으로 한 바퀴씩 서치하면서, 왼쪽으로 빠져나갈 수 있으면 빠져나감.
        int dirNow = 4-d;
        for(int i=dirNow;i<dirNow+4;i++){
            if(board[r+dr[i]][c+dc[i]]==0){
                cleanBoard(r+dr[i],c+dc[i],directions[i]);
                return;
            }
        }

d는 함수의 인풋으로 받은 '현재 바라보고 있는 방향'이고, dirNow를 통해 구한 인덱스를 dr,dc,directions에 대입한 것이 '다음 이동할 방향'이 되게 하였다. 가령 d=0, 즉 북쪽을 보고 있는 경우에는 dirNow = 4, (dr[4],dc[4]) = (0,-1) : 즉 서쪽으로 이동, directions[4]=3: 서쪽... 이런 방식이다.

 

재귀함수는 

1. 한 바퀴 돌면서 갈 곳이 있는지 서치,

2. 한 바퀴 돌면서 갈 곳을 못 찾으면 후진할 수 있는지 확인.

3. 후진 못하면 거기서 종료.

와 같은 논리이다. 

 

여기서 늘 하던 대로 청소해준 칸 = 1, 청소해주지 않은 칸 = 0 으로 만들었다가 낭패를 봤었는데, 그 이유는 벽이 1로 주어지기 때문이다. 

 

한 바퀴를 돌고서도 청소가 안 된 곳을 찾지 못해 후진이 가능한지 여부를 판단할 때, 벽이 있으면 후진을 하지 못하지만 청소가 되어 있는 칸이면 후진할 수 있다. 그래서 청소한 칸은 -1, 벽은 1, 청소가 안 된 칸은 0 으로 구분을 해 주었다.

 

또한 후진방향은 무조건 현재 주어지는 방향에서 두 칸 왼쪽으로 이동한 것이기 때문에, 항상 r+dr[dirNow+1], c+dc[dirNow+1]으로 고정되어 있다. 함수 전체 코드는 아래와 같다.

 

    static void cleanBoard(int r,int c,int d){
        //칸이 청소되어 있는지 확인하고 청소
        if(board[r][c]==0){
            board[r][c]=-1;
            numCleaned++;
        }
        //왼쪽 방향으로 한 바퀴씩 서치하면서, 왼쪽으로 빠져나갈 수 있으면 빠져나감.
        int dirNow = 4-d;
        for(int i=dirNow;i<dirNow+4;i++){
            if(board[r+dr[i]][c+dc[i]]==0){
                cleanBoard(r+dr[i],c+dc[i],directions[i]);
                return;
            }
        }
        //한 바퀴를 돌았음에도 빠져나가지 못했다면, 해당 방향에서 한 칸 후진한 칸에 벽이 있는지 확인함
        //벽이 있으면 함수 탈출, 벽이 없으면 한 칸 후진해서 다시 시작.
        if(board[r+dr[dirNow+1]][c+dc[dirNow+1]]!=1){
            cleanBoard(r+dr[dirNow+1],c+dc[dirNow+1],d);
        }else{
            return;
        }
    }

 

이상 끝. 전체 코드를 첨부하고 마친다.

import java.io.*;

public class BOJ_14503 {
    static int N,M;
    static int[][] board;
    static int numCleaned = 0;
    //북->서->남->동->북->.... = 0->3->2->1 ...
    static int[] directions = {3,2,1,0,3,2,1,0};
    static int[] dr = {0,1,0,-1,0,1,0,-1};
    static int[] dc = {-1,0,1,0,-1,0,1,0};
    //directions[] 배열의 index=현재 보고 있는 방향(0~3), index
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] NM = br.readLine().split(" ");
        N = Integer.parseInt(NM[0]);
        M = Integer.parseInt(NM[1]);

        board = new int[N][M];

        String[] rcd = br.readLine().split(" ");
        int row = Integer.parseInt(rcd[0]);
        int col = Integer.parseInt(rcd[1]);
        int direction = Integer.parseInt(rcd[2]);

        for(int i=0;i<N;i++){
            String[] input = br.readLine().split(" ");
            for(int j=0;j<M;j++){
                board[i][j] = Integer.parseInt(input[j]);
            }
        }
        cleanBoard(row,col,direction);
        System.out.print(numCleaned);
    }

    static void cleanBoard(int r,int c,int d){
        //칸이 청소되어 있는지 확인하고 청소
        if(board[r][c]==0){
            board[r][c]=-1;
            numCleaned++;
        }
        //왼쪽 방향으로 한 바퀴씩 서치하면서, 왼쪽으로 빠져나갈 수 있으면 빠져나감.
        int dirNow = 4-d;
        for(int i=dirNow;i<dirNow+4;i++){
            if(board[r+dr[i]][c+dc[i]]==0){
                cleanBoard(r+dr[i],c+dc[i],directions[i]);
                return;
            }
        }
        //한 바퀴를 돌았음에도 빠져나가지 못했다면, 해당 방향에서 한 칸 후진한 칸에 벽이 있는지 확인함
        //벽이 있으면 함수 탈출, 벽이 없으면 한 칸 후진해서 다시 시작.
        if(board[r+dr[dirNow+1]][c+dc[dirNow+1]]!=1){
            cleanBoard(r+dr[dirNow+1],c+dc[dirNow+1],d);
        }else{
            return;
        }
    }
}