[알고리즘] 백준 - 14503 (로봇 청소기) / 자바

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static int N, M;
    public static int[][] map;
    public static int count = 0;
    
    // 북  동 남 서 쪽
    public static int[] dr = {-1, 0, 1, 0}; 
    public static int[] dc = {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];

        st = new StringTokenizer(br.readLine());
        int r = Integer.parseInt(st.nextToken()); //로봇청소기 좌표y
        int c = Integer.parseInt(st.nextToken()); //로봇청소기 좌표x
        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++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        robot(r, c, d); 
        
//        for (int i = 0; i < N; i++) {
//            for (int j = 0; j < M; j++) {
//                System.out.print(map[i][j]);
//            }
//            System.out.println();
//        }
        
        System.out.print(count);
    }

    public static void robot(int row, int col, int direction) {
    	
        // 빈칸일 경우 청소하고 count+1 
        if (map[row][col] == 0) {
            map[row][col] = 2;
            count++;
        }

             
        int before = direction;
        boolean flag = false;
        
        for (int i = 0; i < 4; i++) {
        	
            //  다음 행선지 
            int nextD = (direction + 3) % 4;
            int nextR = row + dr[nextD];
            int nextC = col + dc[nextD];

            if (nextR > 0 && nextC > 0 && nextR < N && nextC < M) {
            	
            	//청소가 가능하다면 이동
                if (map[nextR][nextC] == 0) {
                    robot(nextR, nextC, nextD);
                    flag = true;
                    break;
                }
            }
            direction = (direction + 3) % 4;
        }

        // 진행 불가할 경우
        if (!flag) {
        	
            int nextD = (before + 2) % 4;
            int nextR = row + dr[nextD];
            int nextC = col + dc[nextD];
     
            if (nextR > 0 && nextC > 0 && nextR < N && nextC < M) {
                if (map[nextR][nextC] != 1) {
                    //후진
                    robot(nextR, nextC, before); 
                }
            }
        }
    }
}