백준 JAVA 14503 로봇청소기 리뷰

제출 코드

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

public class Main {
    static int N, M;
    static int[][] room;
    static int count;
    static int[] dirX={-1,0,1,0}; //북동남서
    static int[] dirY={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());

        room=new int[N][M];

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

        for(int i=0;i<N;i++){
            st= new StringTokenizer(br.readLine());
            for(int j=0;j<M;j++){
                room[i][j]=Integer.parseInt(st.nextToken());
            }
        }
        count=1;
        dfs(r,c,d);
        System.out.println(count);
    }
    static void dfs(int r, int c, int d){
        room[r][c]=-1; //청소 완료

        for(int i=0; i<4; i++){
            d=(d+3)%4;
            int nowx=r+dirX[d];
            int nowy=c+dirY[d];
            //만약 청소되지 않은 칸이 없어서 i++ 되어 다른 칸을 찾더라도 d는 이미 바뀌었기 때문에
            //방향은 이미 90도 돌려짐
            if(nowx>=0&&nowy>=0&&nowx<N&&nowy<M){ //청소되지 않은 칸 찾으면 dfs 호출
                if(room[nowx][nowy]==0){
                    room[nowx][nowy]=-1;
                    count++;
                    dfs(nowx,nowy,d);
                    return; //여기서 return 안하면 dfs 종료되면서 for문 실행할게 남아있으면
                    //실행되면서 다른 곳으로 청소하러 갈 수 있음
                }
            }
        }
        //인접한 4칸 모두 청소 완료시 for문 밖으로 나옴
        //후진 여부, 체크 d 방향은 유지하되 로봇방향은 뒤로 감
        int back=(d+2)%4;
        int bx=r+dirX[back];
        int by=c+dirY[back];

        if(bx>=0&&by>=0&&bx<N&&by<M){
            if(room[bx][by]==-1){
                dfs(bx,by,d);
            }
        }
    }
}

문제 풀이  & 내가 고민하고 어려웠던 점들

왜 dfs/bfs라고 생각했는지?

4방향으로 탐색하면서 청소한 칸 개수를 세는 것이 전형적인 dfs/bfs 문제라고 생각했다.

 

왜 dfs를 선택했는지?

dfs와 bfs 중에서 하나를 고를때 타당한 이유를 대고 정확하게 고르는게 아직 어렵지만  경로에 특징들이 있다고 판단했다. 4칸 중 청소되지 않은 빈칸이 없을때 후진하고, 빈칸 있을땐 90도 회전하는 특징들을 코드로 표현하려면 dfs가 적절하다고 생각했다.

 

어떻게 접근했는지?

문제를 간략하게 요약하면 '청소되지 않은 빈칸이 없는 경우 바라보는 방향 유지하며 후진, 청소되지 않은 칸이 존재하면 반시계로 90도 회전하고 한칸 전진하기' 이다.

 

어려웠던 부분은 반시계로 90도 회전하고 후진하는 것, d를 컨트롤하는 것을 코드로 표현하기 어려웠다. 블로그를 참고하면서 풀었다.

 

1. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 있는 경우,
   1. 반시계 방향으로 90도 회전한다.
   2. 바라보는 방향을 기준으로 앞쪽 칸이 청소되지 않은 빈 칸인 경우 한 칸 전진한다.
   3. 1번으로 돌아간다.

	1
1	로봇 d:1	1
	0

 

로봇이 북쪽을 바라보고 있을때 4칸 중 청소되지 않은 빈칸이 있으므로

주변 4칸을 조사할때마다 90도 회전한다. 2번은 한칸 전진한다 = dfs를 호출한다 로 이해했다.

 

주변 4칸을 조사할때마다 반시계 방향으로 90도 회전해야하는데 어떻게 코드로 표현할 것인가 고민되었다.

d	반시계 방향으로 회전
0 북	3 서
1 동	0 북
2 남	1 동
3 서	2 남

반시계 방향으로 회전하면서 d(바라보는 방향)가 저절로 회전한 방향으로 바뀔 것이다.

위의 표에서 공식을 뽑아내면 (d+3)%4  가 된다.

 

1. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 없는 경우,
   1. 바라보는 방향을 유지한 채로 한 칸 후진할 수 있다면 한 칸 후진하고 1번으로 돌아간다.
   2. 바라보는 방향의 뒤쪽 칸이 벽이라 후진할 수 없다면 작동을 멈춘다.

 

청소 완료한 곳을 -1로 표시했다.

	1
1	로봇 d:1	1
	-1(청소완료)

 

4칸을 모두 조사하고 청소할 수 있는 칸이 나오면 dfs를 호출하고 청소할 수 있는 칸이 없으면 for문이 끝난다. 그 후에 이 후진 작업을 하면 된다. 내가 조금 헷갈렸던게

1. 현재 칸이 아직 청소되지 않은 경우, 현재 칸을 청소한다.

문제에서 이 문장을 보고 후진을 했을 때 청소가 되지 않았다면 개수를 세는 코드를 넣어야하는 거 아닌가? 했었는데 애초에 4칸 모두 조사하고 청소할수 있는 칸이 없어서 나왔기 때문에 괜찮다.

 

d	후진
0 북	2 남
1 동	3 서
2 남	0 북
3 서	1 동

 

후진을 하면 이렇게 되는데 여기서 또 의아했던 점이 d(바라보는 방향)를 유지하면서 후진을 한다면 d는 어차피 유지되는데 뭐하러 d를 가지고 후진하는거지? 라는 생각을 했다.

d는 유지되지만 방향은 후진하면서 변하게 되는데 이를 d 변수를 이용해서 컨트롤하려고 하는 것이었다.

 

위의 표에서 공식을 뽑아내면 (d+2)%4가 된다.

 

이 공식을 통해서 dirX, dirY 인덱스를 불러 방향을 바꾸는 것이었다.

북 0, 동 1, 남 2, 서 3 이랬으니 이에 맞게 dirX, dirY 인덱스를 똑같이 맞춰주면 인접 4칸을 방문할 때 이용할 수 있다.

그래서 나는 아래와 같이 설정했다.

//북동남서
dirX = {-1,0,1,0}; 
dirY = {0,1,0,-1};

0번 인덱스 북, 1번 인덱스 동 이런식으로 

 

헷갈렸던 점(백준 내가 올린 질문 바로가기)

나는 항상 dfs 문제 풀때 배열을 arr[N][M]으로 하면 

int nowx =x+dirX[i];

int nowy =y+dirY[i]; 늘 이런식으로 작성했다

근데 다른 블로그를 보니 코드를 이렇게 짰다.

 

int nowy=r+dirY[d];
int nowx=c+dirX[d];

static void dfs(int r, int c, int d){
        room[r][c]=-1;
       
        for(int i=0;i<4;i++){
            d = (d+3)%4;
            int nowy=r+dirY[d];
            int nowx=c+dirX[d];
            if(nowx>=0&&nowy>=0&&nowx<M&&nowy<N){
                if(room[nowy][nowx]==0){ //청소안된거 찾으면 할일 끝난거
                    room[nowy][nowx]=-1;
                    count++;
                    dfs(nowy,nowx,d);
                    return; //return 하지 않으면 돌아오는 도중에 다른 곳으로 갈 수 있음
                }
            }
        }

 

내가 그동안 코드 짰던거랑 달라서 너무 헷갈렸는데

백준 답변에서 (x,y), (y,x)가 바뀌어도 대칭이기 때문에 기준만 맞으면 된다고 했다.

 

그래서 원래 평소에 짜던 dfs 코드대로 짜고 dirX, dirY만 신경써서 작성했다. 

 

왜 return 을 넣었는지?

dfs를 호출한다는게 다른 곳으로 청소하러 간다는건데 dfs 호출이 종료되면서 return을 안하면 예전 자리에서 대뜸 청소 칸을 찾는 경우가 생긴다. 그래서 return을 해주어서 남아있는 for문이 실행되지 않게끔 했다.

 

 

제가 풀지 못한 문제이고 블로그 보면서 제 나름대로 이해하고 정리해서 풀었던 문제입니다.

틀린 설명이 있다면 꼭꼭 알려주시면 감사하겠습니다!

 

참고했던 블로그들

출처1

출처2

출처3