[백준] 로봇 청소기 14503번 (🥇골드5)

사이트

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

14503번: 로봇 청소기

문제

 

분석

쉬울거 같았지만 매우 헷갈리고 어려웠던 문제였다...

처음에 bfs로 구현할려 했지만 퍼지면서 청소하는 것이 아닌 깊이 있게 가서 청소를 하는 것이 맞아서 

최종적으로 dfs를 선택하였다. 

 

입력은 

첫번째 줄에 청소할 크기를 받고 

두번째 줄에 시작위치와 방향을 입력받는다. 0 북, 1 동, 2 남, 3 서 이다. 

조건을 자세히 봐야 된다. 

3번 조건을 볼때 무조건 직진이 아닌 미로 처럼 돌면서 청소를 한다!! 이 점 유의! 

 

2번 조건을 볼때 4방향 모두가 청소했으면 원래 방향을 유지한 채로 후진을 한다. 단 1 즉 벽을 만났을시 종료가 되어야 된다.

예제에서 주어진 입력을 토대로 하면 다음과 같이 청소기가 작동이 되는 것을 볼 수 있다!

 

형광펜이 칠한 부분을 자세히 보면 

1번까지 갔는데 다 청소가 됐다. 그럼 동쪽 방향을 유지한 채로 2번으로 후진을 하게 된다.

2번에서도 4방향 전부 탐색하게 된다. 이때 3번 방향이 청소가 안되어 있으므로 이번에는 서쪽으로 바꾸고 청소하러 간다.

3번에서는 청소가 완료되고 더 이상 청소할 곳이 없으므로 서쪽 방향을 유지한채 4번으로 후진하게 된다. 

 

즉 이런식으로 프로그램이 구성이 된다는 것이다!!

 

하지만 필자는 전통적인 dfs() 방법인 재귀함수로 if문 조건에 만약 위치하는 곳이 벽이거나 청소한 곳이면 

리턴을 하여 재귀함수를 차례차례 종료 시킬려고 했으나 이 방법으로는 59가 답이 나온다! 즉 0 전체를 청소하게 된다... 

 

즉 필자는 후진을 어떤식으로 구성해야 될지 너무 막막했다. 

 

아래 코드를 통해 차근 차근 풀어나가자.

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

dfs(direction, x, y);
System.out.println(cnt);

다음과 같이 입력을 받고 dfs()를 향해 나아간다. 참고로 direction은 static 변수가 아니다. 해도 상관은 없다. 

 

private static void dfs(int direction, int x, int y) {
    if (arr[x][y] == 0) {
        arr[x][y] = num;
        num++;
        cnt++;

    }
    boolean flag=false;
    int original=direction;
    for (int i = 0; i < 4; i++) {
        direction = (direction + 3) % 4;
        int nX = x + dx[direction];
        int nY = y + dy[direction];

        if (nX >= 0 && nX < n && nY >= 0 && nY < m) {
            if(arr[nX][nY]==0) {
                dfs(direction, nX, nY);
                flag=true;
                break;
            }
        }
    }
   if(!flag){
       int nd=(original+2)%4;
       int nX=x+dx[nd];
       int nY=y+dy[nd];

       if(nX >= 0 && nX < n && nY >= 0 && nY < m){
           if(arr[nX][nY]!=1){
               dfs(original,nX,nY);
           }
       }
   }


}

로직을 푸는 중요의 열쇠인 dfs()함수이다. 자세히보자

 

if (arr[x][y] == 0) {
    arr[x][y] = num;
    num++;
    cnt++;

}

청소하지 않은 칸 즉 0이면 다음과 같이 cnt를 세고 num은 2부터 해서 차례차례 청소했다고 숫자를 배정해준다. 

1로 안둔 이유는 벽이랑 청소한 칸이랑 독립적이기 때문이다.

 

boolean flag=false;
int original=direction;
for (int i = 0; i < 4; i++) {
    direction = (direction + 3) % 4;
    int nX = x + dx[direction];
    int nY = y + dy[direction];

    if (nX >= 0 && nX < n && nY >= 0 && nY < m) {
        if(arr[nX][nY]==0) {
            dfs(direction, nX, nY);
            flag=true;
            break;
        }
    }
}

 

orgianl에다 방향값을 부여한다. 이 변수는 추후 후진할때 쓰기 위함 용도이다. 

for문을 통해 방향대로 돌린다.

direction = (direction + 3) % 4;

이 코드는 반시계 90도를 뜻한다.

 

방향 값을 토대로 dx dy 배열에 대입하여 다음 위치값을 얻어내고 if문으로 입장한다. 

 

이때 1 즉 벽이거나 청소가 되어있는 칸이면.. 

if(!flag){
    int nd=(original+2)%4;
    int nX=x+dx[nd];
    int nY=y+dy[nd];

    if(nX >= 0 && nX < n && nY >= 0 && nY < m){
        if(arr[nX][nY]!=1){
            dfs(original,nX,nY);
        }
    }
}

여기 코드로 오게 된다. 

int nd=(original+2)%4;

이 코드는 후진을 하여 방향을 180도로 바꾸는 코드이다. 동쪽방향이면 서쪽으로 바꾸는 코드! 

근데 만약 벽이면은 아예 코드가 종료되서 사실상 끝이나고 

재귀함수를 호출한 상태에서 벽을 만나면 위 코드에서 

if(arr[nX][nY]==0) {
    dfs(direction, nX, nY);
    flag=true;
    break;
}

 여기서 flag는 true로 바뀌면서 종료가 된다. 

즉 계속 flag가 true로 바뀌기 때문에 

if(!flag){
    int nd=(original+2)%4;
    int nX=x+dx[nd];
    int nY=y+dy[nd];

    if(nX >= 0 && nX < n && nY >= 0 && nY < m){
        if(arr[nX][nY]!=1){
            dfs(original,nX,nY);
        }
    }
}

위 조건문으로 들어오지 못한다!! 

 

전체코드

package implement;

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 Implement14503 {

    static int n;

    static int m;

    static int x;

    static int y;


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

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

    static int[][] arr;

    static int cnt = 0;

    static int num = 2;

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

        st = new StringTokenizer(br.readLine());
        x = Integer.parseInt(st.nextToken());
        y = Integer.parseInt(st.nextToken());
        int direction = Integer.parseInt(st.nextToken());

        arr = new int[n][m];

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

        dfs(direction, x, y);
        System.out.println(cnt);

    }
    private static void dfs(int direction, int x, int y) {
        if (arr[x][y] == 0) {
            arr[x][y] = num;
            num++;
            cnt++;

        }
        boolean flag=false;
        int original=direction;
        for (int i = 0; i < 4; i++) {
            direction = (direction + 3) % 4;
            int nX = x + dx[direction];
            int nY = y + dy[direction];

            if (nX >= 0 && nX < n && nY >= 0 && nY < m) {
                if(arr[nX][nY]==0) {
                    dfs(direction, nX, nY);
                    flag=true;
                    break;
                }
            }
        }
       if(!flag){
           int nd=(original+2)%4;
           int nX=x+dx[nd];
           int nY=y+dy[nd];

           if(nX >= 0 && nX < n && nY >= 0 && nY < m){
               if(arr[nX][nY]!=1){
                   dfs(original,nX,nY);
               }
           }
       }


    }

}

 

결과

 

느낀점

쉬운거 같았지만 복잡했던 문제였다... 삼성 기출문제 및 골드문제라서 그런지 오래걸렸다...  한 3시간 넘게 푼듯 

그래도 맞았으니깐 다행이다 ㅜㅜ