[백준]14503번 로봇 청소기 - Java

문제

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

14503번: 로봇 청소기

 

 

풀이

후,,, 나는 구현 문제가 왜 이렇게 어려운지 모르겠다 ㅠㅠㅠ 많이 풀어봐야 될 듯하다,,

음 뭐랄까 dfs인데 횟수 제한이 있는 dfs 문제?? 2a번 단계가 4번 연속으로 실행되면 멈추거나 후진해야되니까?

 

개인적으로 포인트는

1. 왼쪽으로 돌거나 뒤로 후진할 때의 방향 설정이랑 2. return을 해줘야하는 위치

라고 생각한다!

 

걔네들을 어떻게 했는지는 밑에 코드의 주석을 보면 알 수 있음.

특히 방향 바꾸는 거는 알아두면 다른 문제에서도 편하게 사용가능함!

 

 

코드

// 14503번 로봇 청소기
// https://www.acmicpc.net/problem/14503

package BAEKJOON;

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


// 0: 청소하지 않은 상태
// 1: 벽
// 2: 청소한 상태
public class Num14503_로봇청소기 {
    static int N, M;
    static int answer = 1; // 청소한 구역의 개수(정답)

    static int[][] map;

    // 북동남서(문제에 나와있는대로)
    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));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());

        int r = Integer.parseInt(st.nextToken()); // 로봇 청소기의 r 위치
        int c = Integer.parseInt(st.nextToken()); // 로봇 청소기의 c 위치
        int dir = Integer.parseInt(st.nextToken()); // 로봇 청소기가 바라보고 있는 방향

        map = new int[N][M];

        // 입력
        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 실행
        solution(r, c, dir);

        System.out.println(answer);
    }

    // DFS
    private static void solution(int r, int c, int dir) {
        map[r][c] = 2; // 청소 완료

        // 4번 반복되면 for문 밑에 있는 애들 실행
        for (int i = 0; i < 4; i++) {
            dir = (dir + 3) % 4;
            int nr = r + dr[dir];
            int nc = c + dc[dir];

            if (nr < 0 || nr >= N || nc < 0 || nc >= M) {
                continue;
            }

            // 왼쪽 방향에 청소안한 칸이 있으면 청소
            if (map[nr][nc] == 0) {
                answer++;
                solution(nr, nc, dir);

                return;
            }
        }

        // 위에서 2a단계 4번(for문) 연속 실행되면 뒤쪽 방향 확인
        int backDir = (dir + 2) % 4;
        int br = r + dr[backDir];
        int bc = c + dc[backDir];

        // 바로 뒤쪽이 벽이거나 범위 밖이면 작동 끝(return)
        if (br < 0 || br >= N || bc < 0 || bc >= M || map[br][bc] == 1) {
            return;
        } else { // 뒤쪽으로 후진할 수 있으면 후진
            solution(br, bc, dir);
        }
    }
}