[백준] 14503. 로봇청소기 (골드5) - Simulator

14503. 로봇청소기 (골드5)

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	512 MB	22717	10795	7194	53.821%

문제

로봇 청소기와 방의 상태가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오.
로봇 청소기가 있는 방은 NXM 크기의 직사각형으로 나타낼 수 있으며, 1X1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북 중 하나이다. 방의 각 칸은 좌표 (r, c)로 나타낼 수 있고, 가장 북쪽 줄의 가장 서쪽 칸의 좌표가 (0, 0), 가장 남쪽 줄의 가장 동쪽 칸의 좌표가 (N-1, M-1)이다. 즉, 좌표 (r, c)는 북쪽에서 (r+1)번째에 있는 줄의 서쪽에서 (c+1)번째 칸을 가리킨다. 처음에 빈 칸은 전부 청소되지 않은 상태이다.
로봇 청소기는 다음과 같이 작동한다.

1. 현재 칸이 아직 청소되지 않은 경우, 현재 칸을 청소한다.
2. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 없는 경우,
   2.1.바라보는 방향을 유지한 채로 한 칸 후진할 수 있다면 한 칸 후진하고 1번으로 돌아간다.
   2.2.바라보는 방향의 뒤쪽 칸이 벽이라 후진할 수 없다면 작동을 멈춘다.
3. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 있는 경우,
   3.1.반시계 방향으로 90도 회전한다.
   3.2.바라보는 방향을 기준으로 앞쪽 칸이 청소되지 않은 빈 칸인 경우 한 칸 전진한다.
   3.3. 1번으로 돌아간다.

입력

첫째 줄에 방의 크기
N과 M이 입력된다. (3 <= N, M <= 50) 둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 (r, c)와 처음에 로봇 청소기가 바라보는 방향 d가 입력된다. d가
0인 경우 북쪽, 1인 경우 동쪽, 2인 경우 남쪽, 3인 경우 서쪽을 바라보고 있는 것이다.

셋째 줄부터
N개의 줄에 각 장소의 상태를 나타내는 N X M개의 값이 한 줄에 M개씩 입력된다. i번째 줄의 j번째 값은 칸 (i, j)의 상태를 나타내며, 이 값이 0인 경우 (i, j)가 청소되지 않은 빈 칸이고,
1인 경우 (i, j)에 벽이 있는 것이다. 방의 가장 북쪽, 가장 남쪽, 가장 서쪽, 가장 동쪽 줄 중 하나 이상에 위치한 모든 칸에는 벽이 있다. 로봇 청소기가 있는 칸은 항상 빈 칸이다.

출력

로봇 청소기가 작동을 시작한 후 작동을 멈출 때까지 청소하는 칸의 개수를 출력한다.

예제 입력 1
3 3
1 1 0
1 1 1
1 0 1
1 1 1

예제 출력 1
1

예제 입력 2
11 10
7 4 0
1 1 1 1 1 1 1 1 1 1
1 0 0 0 0 0 0 0 0 1
1 0 0 0 1 1 1 1 0 1
1 0 0 1 1 0 0 0 0 1
1 0 1 1 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 1 0 1
1 0 0 0 0 0 1 1 0 1
1 0 0 0 0 0 1 1 0 1
1 0 0 0 0 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1

예제 출력 2
57

풀이

• 그 자리에서 상태가 유지되며 계속 밑으로 나아간다 => DFS 구성

1. 시계 반대 방향으로 북, 서, 남, 동 순으로 방향배열을 구성한다.
2. 현재 입력받은 방향의 순서가 0-북, 1-동, 2-남, 3-서 순이다.
   방향 배열과 일치시키기 위해 입력받은 수를 연산시켜 바꾼다.
3. 현재 위치에서 확인 - 청소하기 vs 멈추기
   3.1. 현재 위치에 먼지가 있으면 먼지청소 횟수를 늘리고, 다음 방문 방지를 위해 2로 수정
   3.2. 현재 위치가 벽이면 청소기를 멈춘다.
4. 사방에 청소해야 할 곳이 있는지 확인하기
   4.1. 청소 체크 false
   4.2. 90도 반시계 돌면서 이동했을시, 먼지가 있으면 청소를 해야한다고 체크(true)
5. 청소 위치로 이동하기
   5.1. 청소를 해야한다고 체크(true)가 되어 있으면 그 위치와 방향 유지
   5.2. 청소해야 할 곳이 없으면 후진하기

import java.io.*;
import java.util.*;
public class Simulator_14503 {
	static int N, M; // arr size
	static int x, y, d ; //현재 로봇 좌표, 로봇이 바라보고 있는 방향
	//0 - 북, 1 - 서, 2 - 남, 3 - 동 => 반시계방향
	static int[] dx = {-1, 0, 1, 0};
	static int[] dy = {0, -1, 0, 1};
	
	static int[][] arr;
	static int count = 0; // 청소 구역 갯수
	
	public static void main(String[] args) throws IOException{
		// 14503.로봇청소기 (골드5)
		
		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());
		x = Integer.parseInt(st.nextToken());
		y = Integer.parseInt(st.nextToken());
		d = Integer.parseInt(st.nextToken());
		
		arr = new int[N][M];
		
		//board 채워주기
		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());
			}
		}
		
		int xx = x;
		int yy = y;
        // 현재 입력받은 방향의 순서가 0-북, 1-동, 2-남, 3-서 순이다.
        // 방향 배열과 일치시키기 위해 입력받은 수를 연산시켜 바꾼다.
        // 0-북->0-북, 1-동-> 1-서, 2-남->2-남, 3-서->3-동 
		int dd = Math.abs(4-d)%4;
       
		DFS(xx,yy,dd);
        
		System.out.println(count);
		br.close();
	}
	
    // x축, y축, 방향순으로 매개변수를 받는다.
	public static void DFS(int xx, int yy, int dd) {
		
        // 1. 현재 위치에서 확인
		if(arr[xx][yy]==0) { // 현재 위치에 먼지가 있다. 
			count++;
			arr[xx][yy]=2; // 다음 방지를 위해, 위치배열을 2로 바꾼다.
		}else if(arr[xx][yy]==1) {
			return; //더 이상 움직일 곳이 없으면 청소기 멈춘다.
		}
		

		// 2. 사방에 청소해야 할 곳이 있는지 확인하기
		boolean dirty = false; // true면 사방에 청소해야 할 곳이 있다.
        // 다음 위치를 우선 현재 위치로 받아놓는다.
		int nd = dd; 
		int nx = xx;
		int ny = yy;
        
        // 90도 반시계 돌면서 이동했을시, 먼지가 있으면 청소를 해야한다고 체크
		for(int i=1; i<=4; i++) {
			nd = (dd+i)%4;
			nx = xx + dx[nd];
			ny = yy + dy[nd];
			if(nx>0 && ny >0 && nx <N && ny<M &&arr[nx][ny]==0) {
				dirty = true;
				break;
			}
		}

		3. 청소 위치로 이동하기
		if(dirty) { // 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 있는 경우 유지
			xx = nx;
			yy = ny;
			dd = nd;
		}else { // 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 없는 경우, 바라보는 방향을 유지한 채로 한 칸 후진.
			nd = Math.abs(dd+2)%4; // 후진을 위해 잠시 방향만 수정
			nx = xx + dx[nd];
			ny = yy + dy[nd];
			
			xx = nx;
			yy = ny;	
			dd = dd; //방향 다시 원래대로 바꿔놓기
		}
		
		DFS(xx,yy,dd);
	}
}

* 방향이 어떻게 변해가는지 확인하여 바꿔주는 식을 작성한다.