[백준] 14503 로봇 청소기

풀이

clean(int row, int col, int direction){

1. 현재 위치를 청소
2. 4개의 방향 돌면서 탐색하며 청소 
3. 4개의 방향 모두 청소가 되어있거나 벽이면
	- 바라보는 방향 유지한채 후진하고 왼쪽 방향으로... clean
    - 후진할 수 없는 경우 그대로 종료
    

}

청소한 곳은 2로 설정

이때 4개의 방향

• 왼쪽을 바라보고 청소하는 경우
  1 -> 0
  2 -> 1
  3 -> 2
  0 -> 3
  -1 하면 되지만, 0(북)의 경우 -1하면 범위를 벗어나므로
  (방향 + 3) % 4
• 후진하고 왼쪽을 바라보는 경우
  1 -> 3 쪽으로 이동
  2 -> 0
  3 -> 1
  0 -> 2
  현재 바라보고 있는 방향에 따라 후진하는 위치도 달라짐!
  (방향 + 2) % 4

코드

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

/**
 * 
 * @author juyoung
 * 현재 방향을 어떻게 나타낼 것인가?
 * 
 * 왼쪽 회전
 * 0 -> 3
 * 1 -> 0
 * 2 -> 1
 * 3 -> 2
 * 1씩 감소하지만 0은 범위를 벗어나므로 (방향+3) % 4 해줌
 * 
 * 후진 후 왼쪽 회전
 * 보는 방향 그대로 후진하고 왼쪽 회전하면 
 * 현재 위치 입장에서는 현재 방향의 반대
 * 0 -> 2
 * 1 -> 3
 * 2 -> 0
 * 3 -> 1
 * (방향+2) % 4
 * 
 * r 은 위에서부터의 거리임을 주의
 */
	
public class Main {

	public static int N, M;
	public static int[][] map;
	public static int cnt = 0;
	
	public static int[] dr = {-1, 0, 1, 0};
	public static int[] dc = {0, 1, 0, -1}; // 북동남서, 0123
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st;
		
		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());
		int c = Integer.parseInt(st.nextToken());
		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());
			}
		}
		
		clean(r, c, d);
		
		System.out.println(cnt);

	}
	
	public static void clean(int r, int c, int d) {
		
		// 현재 위치 청소
		if(map[r][c] == 0) {
			map[r][c] = 2; //청소
			cnt++; // 청소한 칸의 갯수
		}
		
		// 왼쪽 방향부터 차례대로 탐색 진행
		boolean flag = false; // 청소할 곳이 존재하는지 확인 
		int origin = d; 
		
		for(int i=0; i<4; i++) {
			// 4가지 방향으로 돌면서 확인할 수 있기 때문에 4번 탐색
			int next_d = (d+3) % 4; // 현재 방향을 기준으로 탐색
			int next_r = r + dr[next_d];
			int next_c = c + dc[next_d];
			
			if(next_r > 0 && next_c > 0 && next_r < N && next_c < M) {
				if(map[next_r][next_c] == 0 ) {
					//청소가 안 된 곳이라면
					clean(next_r, next_c, next_d);
					flag = true;
					break;
				}
			}
			d = (d + 3) % 4; // 청소를 마쳤거나 왼쪽 방향에 청소할 공간이 없을 때 그 방향으로 회전
		}
		
		if(!flag) {
			// 네 방향 모두 청소가 되어있거나 벽인 경우
			int next_d = (origin + 2) % 4; // 후진할 방향
			int next_r = r + dr[next_d];
			int next_c = c + dc[next_d];
			
			if(next_r > 0 && next_c > 0 && next_r < N && next_c < M) {
				if(map[next_r][next_c] != 1) {
					//후진할 곳이 벽이 아닌 경우
					clean(next_r, next_c, origin); // 바라보는 방향 유지한채 후진
				}
			}
		}
	}

}