[백준]14503_로봇청소기

[문제 링크]

boj 14503 로봇청소기 구현

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

14503번: 로봇 청소기

 

[생각 흐름]

처음에는 문제의 조건대로 각 케이스별로 하려 하였으나 케이스를 묶을 수 있어서 묶어서 풀이하였다.

문제의 조건 2번의 말은 결국 현재 위치에서 왼쪽으로 돌면서 청소가 안되어있으면 가고 청소가 되어 있거나 벽이면 또다시 왼쪽으로 돌아서 확인한다는 것이다.

따라서 처음 시작 dir에서 왼쪽으로 돌아가며 벽이 아닌데 청소가 안되어 있는 경우에는 멈추고 다시 재귀적으로 반복할 수 있게 하였다.

만약 4방향 모두가 벽이거나, 벽은 아니지만 청소가 되어있으면 왔던 길로 되돌아가는데 되돌아가는 길이 벽이라면 멈추고, 아니라면 돌아가도록 구성하였다.

 

[코드]

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

/*
로봇청소기 작동법
1.현재 위치를 청소한다.
2.현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다.
    왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.
    왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.
    네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.
    네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.

 d가 0인 경우에는 북쪽을, 1인 경우에는 동쪽을, 2인 경우에는 남쪽을, 3인 경우에는 서쪽을 바라봄
 */

public class Main {
    private static int arr[][];
    private static int cnt = 0;
    private static boolean visit[][];
    private static int[] dirx = {-1, 0, 1, 0}; //북,동,남,서
    private static int[] diry = {0, 1, 0, -1};

    private static void solution(int x, int y, int dir) {
        int nowleft=dir; 
        int nowx = x;
        int nowy = y;

        boolean f = true;
        for (int i = 0; i < 4; i++) {
            nowleft = (nowleft - 1 == -1) ? 3 : nowleft - 1; //현재 위치에서 -1하면 왼쪽의 dir이 나온다.
            nowx = x + dirx[nowleft];
            nowy = y + diry[nowleft];

            if (nowx < 0 || arr.length <= nowx || nowy < 0 || arr[0].length <= nowy) continue;//범위를 넘어감(벽)
            if (arr[nowx][nowy] == 0 && !visit[nowx][nowy]) {  //벽이 아닌데 청소가 되어있지 않은경우 
                f = false; 
                break;
            }
        }

        if (!f) { //벽이 아닌데 청소가 되어있지 않은경우 
            visit[nowx][nowy] = true;
            cnt++;
            solution(nowx, nowy, nowleft); 
        } else {
            nowx = x - dirx[dir];
            nowy = y - diry[dir];
            if (nowx < 0 || arr.length <= nowx || nowy < 0 || arr[0].length <= nowy||arr[nowx][nowy] == 1  ) return; 
            //범위를 벗어나는 경우(벽), 자신의 길로 돌아가는 길이 벽이면 멈춤 
            else solution(nowx, nowy, dir);
            //후진해서 돌아가서 확인
        }

    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        arr = new int[n][m];
        visit = new boolean[n][m];

        st = new StringTokenizer(br.readLine());
        int x = Integer.parseInt(st.nextToken());
        int y = Integer.parseInt(st.nextToken());
        int dir = Integer.parseInt(st.nextToken());

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        visit[x][y] = true;
        cnt = 1;
        solution(x, y, dir);

        System.out.println(cnt);
    }
}