문제 정리

---

로봇 청소기가 N * M 크기의 방을 규칙에 따라 청소한다
청소기가 청소하는 칸의 개수를 구하는 것이 목표다

작동 규칙은 다음과 같다

1. 현재 위치 청소
2. 현재 방향 기준 왼쪽 방향을 탐색한다
   2-1. 청소가 되어 있지 않으면 탐색한 방향으로 회전하고 한 칸 전진 후 1번으로 돌아감
   2-2. 탐색한 방향에 청소를 할 수 없으면 방향만 탐색 방향으로 회전하고 2번으로 돌아감
   2-3. 네 방향 모두 청소가 돼 있거나 벽인 경우, 바라보는 방향 유지, 후진 한칸 후 2번으로 돌아감
   2-4. 네 방향 모두 청소가 돼 있거나 벽인 경우, 후진이 불가능하면 작동 멈춤

입력

행크기 열크기
로봇행위치 로봇열위치 로봇방향
맵 상태

맵에서
0은 청소가 안된 칸
1은 벽

로봇의 방향은
0 -> 북
1 -> 동
2 -> 남
3 -> 서

주어진 로봇의 위치는 항상 청소가 안된 칸

출력

로봇청소기가 청소한 칸 수

idea 정리

---

문제 설명의 작동 원리는 2번을 읽어도 무슨 말인지 잘 이해가 안갔다
특히 2-2에서 그 방향으로 회전하라는 말이 모호하다고 생각했다
그래서 인터넷에서 문제를 조금 풀어서 설명한 글도 찾아서 읽어보고
질문글에서 다르게 표현한 글도 읽어보니까 이해가 갔다

작동 순서를 그림으로 간단히 표현해봤다

이해를 하고 보니 작동원리만 정확히 구현하면되는 문제였다
어느 시뮬레이션 문제에서와 같이 작동 순서를 쪼갈라서 구현했다

이 문제를 dfs로 풀었다고 생각했는데
dfs라고 하기에는 연결된 모든 분기를 모두 탐색하는게 아니라
정답이 되는 가지만 탐색하는거라 헷갈려서 찾아봤다
백준 질문글에서 나랑 비슷하게 구현한 글을 봤는데
14503 질문글
답변을 달아주신 분이 dfs보단 greedy에 가깝다고 했다

알고리즘 정리

---

1. 현재 위치 청소
2. 4방향으로 회전하면서 현재 방향 기준 왼쪽에 청소할 칸이 있는지 탐색
   2-1. 청소할 칸이 있으면 전진하고 1로 돌아감
3. 4방향 다 청소할 칸이 없거나 벽이 있으면 방향 유지한 채로 후진
   3-1. 후진 불가시 작동 멈춤

구현

---

//로봇 청소기
public class Main {
	static int N,M,res;
	static int[][] map;
	static int r, c, direction;
	
	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));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		st = new StringTokenizer(br.readLine(), " ");
		r = Integer.parseInt(st.nextToken());
		c = Integer.parseInt(st.nextToken());
		direction = 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++) {
				int value = Integer.parseInt(st.nextToken());
				map[i][j] = value;
			}
		}
		
		run();
		
		bw.write(res + "");
		bw.flush();
		bw.close();
		br.close();
	}
	
	static public void clean() {
		map[r][c] = 2;
	}
	
	static public int checkDirty() {
		int d = direction;
		
		for(int i=0; i<4; i++) {
			int nd = (d + 3)%4;		//현재 방향 기준 왼쪽 공간을 검사함
			int nr = r + dr[nd];
			int nc = c + dc[nd];
			
			if(0 <= nr && nr<N && 0<=nc && nc<M) {
				if(map[nr][nc]==0)
					return nd;		//청소할 곳 있음
			}
			d = nd;		//청소를 못하더라도 방향을 돌림
		}
		return -1;
	}
	
	static public void run() {
		if(map[r][c]==0) {
			res++;
			clean();
		}
		
		int dirtyD = checkDirty();
		if(dirtyD!=-1) {		//청소할 곳이 있으면 그 방향으로 전진
			direction = dirtyD;
			r += dr[direction];
			c += dc[direction];
			
			run();
			return;
		}
		else {			//청소할 곳이 없으면 뒤로 후진
			int d = (direction + 2)%4;
			int nr = r + dr[d];
			int nc = c + dc[d];
			
			if(0 <= nr && nr<N && 0<=nc && nc<M) {
				if(map[nr][nc]!=1) {
					r = nr;
					c = nc;
					run();
				}
			}
		}
	}
}

결과

---