백준 14503 로봇 청소기 자바

문제는 다음과 같다
https://www.acmicpc.net/problem/14503

풀이는 다음과 같다

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

public class Main {
  
    static int[][] map;
    
    //정답 보여줄 answer
    static int answer = 0;
    
    static boolean[][] visited;
    
    static int R,C;
    
    //상 우 하 좌 dr dc, 여기는 행열. 맨 왼쪽 위 00 시작. (북동남서) = 상 좌 하 우 / 후진은 +2, 반시계90도는 +3
    static int[] dr = {-1, 0, 1, 0};
    static int[] dc = {0, 1, 0, -1};
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st1 = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st1.nextToken());
        C = Integer.parseInt(st1.nextToken());
        map = new int[R][C];
        visited = new boolean[R][C];

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

        for(int i = 0 ; i < R ; i++) {
            StringTokenizer st3 = new StringTokenizer(br.readLine());
            for(int j = 0 ; j < C ; j++) {
                map[i][j] = Integer.parseInt(st3.nextToken());
            }
        }

        clean(r, c, d);

        bw.write(String.valueOf(answer));
        bw.flush();
        bw.close();


    }
    
    
    static boolean isValid(int r, int c) { //index유효한지, 갈수잇는 0인지
        if(0 > r || r >= R || 0 > c || c >= C || map[r][c] != 0) return false;
        return true;
    }



    static void clean(int r, int c, int d) {
        if(map[r][c] == 0 && !visited[r][c]) {
            answer++;
            visited[r][c] = true;
        }

        if(checkAround(r, c, d)) {
            for(int i = 0 ; i < 4 ; i++) {
                d = (d+3) % 4;
                int nr = r + dr[d];
                int nc = c + dc[d];

                if(isValid(nr, nc) && !visited[nr][nc]) {
                    clean(nr, nc, d);
                    break;
                }
            }
        }
        else {
            int nr = r + dr[(d+2)%4];
            int nc = c + dc[(d+2)%4];

            if(isValid(nr, nc)) {
                clean(nr, nc, d);
            }
            else {
                return;
            }
        }
    }

    static boolean checkAround(int r, int c, int d) { //주위 네칸중 청소할수있는 칸 여부
        for(int i = 0 ; i < 4 ; i++) {
            if(isValid(r + dr[i], c + dc[i]) && !visited[r + dr[i]][c + dc[i]]) return true;
        }
        return false;
    }


}

어.. 풀이들을 보면 DFS라고 하지만, 나는 약간 구현에 더 가까운것 같다.

문제를 읽으며 순서만 제대로 파악한다면,
충분히 맞출 수 있는 문제이다.

1. 청소가 안되어있다면 청소를 해준다.

if(map[r][c] == 0 && !visited[r][c]) {
            answer++;
            visited[r][c] = true;
        }

2. 주위 네개의 칸에 청소 가능한 칸이 있는지 체크한다 (checkAround)

static boolean checkAround(int r, int c, int d) { //주위 네칸중 청소할수있는 칸 여부
        for(int i = 0 ; i < 4 ; i++) {
            if(isValid(r + dr[i], c + dc[i]) && !visited[r + dr[i]][c + dc[i]]) return true;
        }
        return false;
    }

3. 있다면 청소가능한 앞칸을 찾을때까지 반시계 90회전하고 앞칸을 체크한다. 청소 가능한 칸을 찾으면 그 칸을 청소한다.
   (여기서, 초기상태에 앞칸체크가 아니라 반시계 90을 먼저 해줘야 한다.)

if(checkAround(r, c, d)) {
            for(int i = 0 ; i < 4 ; i++) {
                d = (d+3) % 4;
                int nr = r + dr[d];
                int nc = c + dc[d];

                if(isValid(nr, nc) && !visited[nr][nc]) {
                    clean(nr, nc, d);
                    break;
                }
            }
        }

4. 없다면(주위 네 칸이 청소 다 되어있거나 청소할 수 있는 칸이 없다면)
   방향을 유지한채로
   후진 가능하다면 1번으로 돌아가고, 불가능하다면 작동을 멈춘다

else {
            int nr = r + dr[(d+2)%4];
            int nc = c + dc[(d+2)%4];

            if(isValid(nr, nc)) {
                clean(nr, nc, d);
            }
            else {
                return;
            }
        }

약간 이런 문제들을 잘 풀어야 구현에서 유리할 것 같다.
화이팅

ps.
처음에 dr, dc 배열을 시계방향으로 잡았기 때문에,
d = (d+2)%4 가 반대방향,
d = (d+3)%4 가 반시계방향이다.