[BOJ] 14503 로봇청소기 - Java

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

14503번: 로봇 청소기

---

1. 문제

NxM크기의 맵에서 주어진 조건에 맞게 로봇청소기가 이동한다.

로봇청소기가 작동을 멈출 때까지 청소하는 칸의 개수를 출력한다.

[조건]

1. 현재칸 주변 4칸 탐색 시 (반복)

 - 현재 방향 기준 반시계 방향으로 90도 회전

 - 바라보는 방향을 기준으로 앞 칸이 비어있으면 앞 칸으로 전진한다.

2. 주변 4칸 모두 갈 수 없는 경우

 - 바라보는 방향을 유지한 채 한 칸 후진 후 재탐색

 - 한 칸 후진하면 벽인 경우 로봇청소기 작동 멈춤.

 

2. 풀이

dfs로 풀었다.

주의할 점은 3가지이다.

1. 방향

2. return

3. 후진

 

1.방향

방향은 문제에서 북->동->남->서 순서로 0123으로 설정해주었다.

하지만 함정인게, 현재 방향 기준으로 반시계방향으로 90도 회전한 방향을 탐색해야 한다.

그래서 4번 반복하지만 실제로 보는 방향은 (시작방향+3)%4 로 반시계방향으로 90도 회전한 방향을 본다.

=> 4번 반복하는 이유는 매 턴마다 갱신된 방향 기준으로 반시계방향 90도로 또 갱신이 되어 4번 반복하면 모든 방향을 보게 된다.

 

2. return

4방탐색 중 return 해주지 않으면 문제 조건에 맞는 방향대로 dfs 해줬다가 dfs 다 끝나고 돌아오는 길에

return이 안되어있어서 다른 방향으로 새게 된다. 때문에 다른 방향은 보지 않아도 되므로 return을 해준다.

 

3. 후진

그리고 4방탐색하는 for문이 끝나고 다음 줄로 넘어왔다는 건 4방이 다 차있다는 의미이므로 이제 후진을 해줘야 한다.

후진하는 방향은 제일 최근에 갱신된 방향을 기준으로 반대방향으로 dy, dx를 더한 좌표로 이동한다.

단, 바라보는 방향은 갱신된 방향 그대로 본다. 이동만 반대방향으로 해준다.

반대방향 = (갱신된 현재 방향 + 2) % 4 

 

 

3. 코드

package BOJ;

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

public class BOJ_14503_로봇청소기 {

    static int[][] map, visited;
    static int N, M, ans, sy, sx, sd;

    static int[] dy = {-1,0,1,0};   //북동남서
    static int[] dx = {0,1,0,-1};

    public static void main(String[] args) throws Exception {
        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 int[N][M];

        st = new StringTokenizer(br.readLine());
        sy = Integer.parseInt(st.nextToken());
        sx = Integer.parseInt(st.nextToken());
        sd = 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());
            }
        }

        ans = 1;
        dfs(sy, sx, sd);
        System.out.println(ans);
    }

    static void dfs(int sy, int sx, int sd) {
        visited[sy][sx] = 1;

        for (int d=0; d<4; d++) {
            sd = (sd+3) % 4;    //현재 방향 기준 반시계방향 90도 회전 -> 매 턴마다 바뀜 -> 결국 한 바퀴
            int ny = sy+dy[sd];
            int nx = sx+dx[sd];
            if (ny<0 || ny>=N || nx<0 || nx>=M || map[ny][nx]==1 || visited[ny][nx]==1) continue;
            ans++;
            visited[ny][nx] = 1;
            dfs(ny, nx, sd);
            return; //리턴해주지 않으면 dfs 끝나고 다시 돌아오면서 다른 방향으로 새게 된다.
        }

        //네 방향 모두 청소했을 때 현재지점에서 후진
        int bd = (sd+2) % 4;
        int by = sy+dy[bd];
        int bx = sx+dx[bd];
        if (by>=0 && by<N && bx>=0 && bx<M && map[by][bx]!=1) {
            dfs(by, bx, sd);
        }
    }
}

 

4. 사담

감을 되찾자

알고리즘 재밌다..