[backjoon]14503 로봇청소기 java

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

14503번: 로봇 청소기

먼저 boolean타입의 2차원 배열을 이용하여 청소한 부분을 확인해주고 계속해서 현재 위치를 끌고 나갔다.
청소가 안 되었다면 청소를 해주고,(marked = true)
왼쪽 방향(현재 방향을 기준으로 반시계 방향)에 청소를 해야한다고 할때, 새로운 좌표가 청소를 안 한 상태에 청소를 할 수 있다면 새로운 좌표로 다시 탐색 해주었다.
반대로 청소를 완료했거나 청소를 할 수가 없다면(벽이라서) 현재 위치는 그대로 둔 채 회전만 진행하여 다시 탐색을 진행하였다.(C)

 

 

import java.io.*;
import java.util.*;
 
/**
 * DFS를 이용해서 완전 탐색해야 하는 문제
 * 방향 설정이 되게 중요하다.
 **/
class Main {
    static boolean[][] marked;
    static int[][] dirs = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } }; //북 동 남 서
    static int N, M, answer;
    static int[][] map;
 
    public static void main(String[] args) throws Exception {
        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());
        marked = new boolean[N][M];
        map = new int[N][M];
 
        st = new StringTokenizer(br.readLine());
        int curR = Integer.parseInt(st.nextToken());
        int curC = 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++) {
                int cur = Integer.parseInt(st.nextToken());
                map[i][j] = cur;
            }
        }
 
        clean(0, d, curR, curC);
        System.out.println(answer);
    }
 
    public static void clean(int cnt, int d, int curR, int curC) {
        if (cnt == 4) { // 4방향 청소가 다 됨.
            int nextD = (d +2) %4;
            int nextR = curR + dirs[nextD][0];
            int nextC = curC + dirs[nextD][1];
            // D : 뒤쪽이 벽인 경우들
            if (nextR < 0 || nextC < 0 || nextR >= N || nextC >= M)
                return;
            if (map[nextR][nextC] == 1) {// 벽
                return;
            }
            // C
            clean(0, d, nextR, nextC);
            return;
        }
 
        // 현재위치 청소
        if (!marked[curR][curC]) {
            marked[curR][curC] = true;
            answer++;
        }
        //왼쪽부터 즉, 시계 반시계 방향으로 회전하며 탐색해야한다.
        int nextD = (d + 3) % 4;
        int nextR = curR + dirs[nextD][0];
        int nextC = curC + dirs[nextD][1];
 
        // 청소가 되지 않았고, 청소를 할 수 있다면 한칸 전진!!
        if (!marked[nextR][nextC] && map[nextR][nextC] == 0) {
            clean(0, nextD, nextR, nextC);
            return;
        }
        // 청소가 이미 되었고, 뒤쪽이 벽이지만 후진해서 이동 할 수 있는 겅우!!
        if (marked[nextR][nextC] || map[nextR][nextC] == 1) {
            clean(cnt + 1, nextD, curR, curC);
            return;
        }
    }
}