(JAVA) [BOJ]백준 14503번, 로봇 청소기

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

14503번: 로봇 청소기

 

14503, 로봇 청소기

📌 [ 난이도 : 골드 5 ]

이번 문제는 DFS 로 풀이를 진행했다.

문제 읽고 이해하는데만 한 세월 걸린 문제 !

 

📚 Process

초기화 및 선언

: 청소할 구역에 대한 범위를 입력받고 시작 좌표와 방향을 받는다. 방향이 중요하기 때문에 dir 도 신경써서 선언해주어야 한다.

static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
static int[][] dir = {{-1,0},{0,1}, {1,0},{0,-1}};
static int[][] map;
static int N, M, sx, sy, way, time=1;
public static void main(String[] args) throws IOException {
    input();
    pro();
}

public static void input() throws IOException {
    StringTokenizer st = new StringTokenizer(br.readLine(), " ");
    // 좌표 생성
    N = Integer.parseInt(st.nextToken()); // Y좌표
    M = Integer.parseInt(st.nextToken()); // X좌표
    map = new int[N][M];

    // 시작 좌표 & 방향 설정
    st = new StringTokenizer(br.readLine(), " ");

    sy = Integer.parseInt(st.nextToken());
    sx = Integer.parseInt(st.nextToken());
    way = 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());
        }
    }
}

 

구현(DFS)

: 헷갈리는 부분이 후진을 하는 경우에 청소를 했던 구역을 방문해도 되는가 ? 결론은 재방문을 해도 된다.

또한 반시계 방향으로 탐색을 진행하다 보니 way 에 대한 검증도 확실하게 해야 한다.

또한 dfs 로 갈 수 있는 구역을 먼저 탐색한 후 돌아왔을 때, return을 해서 더 이상 움직이는 상황을 방지해 주어야 한다.

후진할 대만 이전 길을 되돌아 가며 확인할 수 있기 때문이다.

// x, y, 방향
static void dfs(int x, int y, int way) {
    // 청소를 했다는 의미
    map[y][x] = 2;

    for(int k=0; k<4; k++) {
        way -= 1; // 왼쪽 방향으로 탐색
        if(way == -1) way = 3;

        int nx = x + dir[way][1];
        int ny = y + dir[way][0];

        if(nx<0 || ny<0 || nx>=M || ny>=N) continue;
        if(map[ny][nx] != 0) continue;

        time++;
        dfs(nx, ny, way);
        /*
         * 일반적인 dfs는 가다가 길이 막히면 다시 되돌아와서 해당 위치부터 계산하지만
         * 이 문제는 후진할 때만 이전 길을 되돌아 가며 확인할 수 있으므로
         * return을 해서 다시 되돌아 와도 더 이상 움직이면 안된다!
         */
        return;
    }

    // 더 이상 청소할 공간이 없기 때문에 반복문을 빠져나온 상황
    // 반대방향으로 후진해야 한다
    int d = (way+2)%4; 
    int bx = x + dir[d][1];
    int by = y + dir[d][0];

    // 범위 OUT & 이미 이미 청소된 곳(구동하고 나서 청소한 곳이 아닌!) 의 경우엔 return
    if(bx<0 || by<0 || bx>=M || by>=N || map[by][bx] == 1) return;
    // 후진할 때 방향 유지
    dfs(bx, by, way);
}

 

 

✅ 전체 코드

: 문제 해석부터 애를 먹었던 문제 🤣

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int[][] dir = {{-1,0},{0,1}, {1,0},{0,-1}};
    static int[][] map;
    static int N, M, sx, sy, way, time=1;
    public static void main(String[] args) throws IOException {
        input();
        pro();
    }

    public static void input() throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        // 좌표 생성
        N = Integer.parseInt(st.nextToken()); // Y좌표
        M = Integer.parseInt(st.nextToken()); // X좌표
        map = new int[N][M];

        // 시작 좌표 & 방향 설정
        st = new StringTokenizer(br.readLine(), " ");

        sy = Integer.parseInt(st.nextToken());
        sx = Integer.parseInt(st.nextToken());
        way = 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());
            }
        }
    }

    public static void pro(){
        dfs(sx,sy,way);
        System.out.println(time);
    }

    // x, y, 방향
    static void dfs(int x, int y, int way) {
        // 청소를 했다는 의미
        map[y][x] = 2;

        for(int k=0; k<4; k++) {
            way -= 1; // 왼쪽 방향으로 탐색
            if(way == -1) way = 3;

            int nx = x + dir[way][1];
            int ny = y + dir[way][0];

            if(nx<0 || ny<0 || nx>=M || ny>=N) continue;
            if(map[ny][nx] != 0) continue;

            time++;
            dfs(nx, ny, way);
            /*
             * 일반적인 dfs는 가다가 길이 막히면 다시 되돌아와서 해당 위치부터 계산하지만
             * 이 문제는 후진할 때만 이전 길을 되돌아 가며 확인할 수 있으므로
             * return을 해서 다시 되돌아 와도 더 이상 움직이면 안된다!
             */
            return;
        }

        // 더 이상 청소할 공간이 없기 때문에 반복문을 빠져나온 상황
        // 반대방향으로 후진해야 한다
        int d = (way+2)%4; 
        int bx = x + dir[d][1];
        int by = y + dir[d][0];

        // 범위 OUT & 이미 이미 청소된 곳(구동하고 나서 청소한 곳이 아닌!) 의 경우엔 return
        if(bx<0 || by<0 || bx>=M || by>=N || map[by][bx] == 1) return;
        // 후진할 때 방향 유지
        dfs(bx, by, way);
    }
}