[java]로봇 청소기 - 백준14503

문제

• 로봇 청소기(백준14503)

풀이

문제 해석을 하자면,

• 주어진 문제의 조건에 맞춰서 로봇 청소기가 청소한 칸 수를 구하자

풀이

• 조건에 맞춰서 단순 “구현”하면 되는 문제이다.
• 본인은 재귀를 활용하여 구현하였다.
  • 조건들에 맞게 구현 -> “주석 참고”

코드

public static int[][] inArr = new int[52][52];
public static boolean[][] visited = new boolean[52][52];
public static int[] dx = {-1, 0, 1, 0}; // 북 동 남 서
public static int[] dy = {0, 1, 0, -1};
public static int N, M;

public static void dfs(int cx, int cy, int dir) {
    //base condition -> 범위, 벽체크 + "후진 불가시"
    if(cx<0||cy<0||cx>=N||cy>=M) return;
    if(inArr[cx][cy]==1) return;
    visited[cx][cy] = true; // 방문표시=청소표시
    //recursion
    boolean cleaning = false;
    for(int i=0; i<4; i++) {
        int nx = cx+dx[i];
        int ny = cy+dy[i];
        if(nx<0||ny<0||nx>=N||ny>=M) continue;
        if(inArr[nx][ny]==1) continue;
        if(visited[nx][ny]) continue;
        // 0이면서 첫 방문이라면,
        cleaning = true;
    }
    // cleaning 에 따라 문제에서 주어진 조건 적용
    if(cleaning) {
        // 1. 반시계 90도
        if(dir-1<0) dir=3;
        else dir = dir-1;
        // 2. 바라보는 방향 "0이면서 첫방문" 이면 전진
        int nx = cx+dx[dir];
        int ny = cy+dy[dir];
        if(inArr[nx][ny]==0 && !visited[nx][ny]) {
            // 3. 재귀
            dfs(nx, ny, dir);
        }else {
            // 3. 재귀
            dfs(cx, cy, dir);
        }
    }else {
        int temp = dir;
        dir = (dir+2)%4; // 180도 회전(후진방향)
        // 후진방향 "0이면서 중복방문" 이면 후진가능
        int nx = cx+dx[dir];
        int ny = cy+dy[dir];
        if(inArr[nx][ny]==0 && visited[nx][ny]) {
            // 1. 후진 가능시 후진 후 재귀
            dfs(nx, ny, temp); // 방향은 유지(temp)
        }
        else {
            // 2. 후진 불가시 작동 종료
            return;
        }
    }
}

public static void main(String[] args) throws Exception {
    //input
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
    N = Integer.parseInt(stk.nextToken());
    M = Integer.parseInt(stk.nextToken());
    stk = new StringTokenizer(br.readLine(), " ");
    int cx = Integer.parseInt(stk.nextToken());
    int cy = Integer.parseInt(stk.nextToken());
    int dir = Integer.parseInt(stk.nextToken());
    for(int i=0; i<N; i++) {
        stk = new StringTokenizer(br.readLine(), " ");
        for(int j=0; j<M; j++) {
            int num = Integer.parseInt(stk.nextToken());
            inArr[i][j] = num;
        }
    }
    //run
    dfs(cx, cy, dir);
    //output -> visited 로 도출
    int result = 0;
    for(int i=0; i<N; i++) {
        for(int j=0; j<M; j++) {
            if(visited[i][j]) result++;
        }
    }
    System.out.println(result);
}

느낀점

생략