> For the complete documentation index, see [llms.txt](https://heunnajo.gitbook.io/algorithms-problem-solving-skills/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://heunnajo.gitbook.io/algorithms-problem-solving-skills/undefined-1/undefined-12.md).

# 로봇 청소기

문제의 핵심 : 현재 위치와 방향이 계속 변화하고, 왼쪽 방향 먼저 탐색(&청소)한다!\
델타어레이로 왼쪽 방향, 뒤쪽 방향 전환 시 변화하는 방향 일반화⭐️⭐️⭐️⭐️⭐️\
현재 방향을 d라고 할 때, 왼쪽 방향은 d+3이다.하지만 4가지 방향으로서 4개만 존재하고, 4개 단위로 숫자가 0부터 시작하기 때문에 이 역시 모듈러 연산을 생각해서 이용해줘야한다!!!

뒤쪽도 마찬까지로, 현재 방향이 d라고 하면, 뒤쪽 방향은 d+2이다. 하지만 4가지 방향만 존재하기 때문에 4로 나눈 나머지값, 모듈러 연산을 이용하면 쉽게 구할 수 있다!!!

| 현재위치 | 왼쪽 = (현재 위치+3)%4 | 뒤쪽 = (현재 위치+2)%4 |
| ---- | ---------------- | ---------------- |
| 0(북) | 3 = (0+3) % 4    | 2 = (0+2) % 4    |
| 1(동) | 0 = (1+3) % 4    | 3 = (1+2) % 4    |
| 2(남) | 1 = (2+3) % 4    | 0 = (2+2) % 4    |
| 3(서) | 2 = (3+3) % 4    | 1 = (3+2) % 4    |

알고리즘 : 왼쪽 방향부터 탐색, 그왼쪽좌표에서 재귀적으로 반복한다!\
\=>반시계방향으로 **상하좌우 인접 칸 탐색&청소**한다!!!⭐️⭐️⭐️⭐️⭐️\
\=>for(i=0;i<4;i++) 으로 4가지 방향에 대해서 반복하고, i=x번째에서 왼쪽 좌표칸 청소 못한다면 방향만 전환해주고 i = i++ 함으로써 문제의 2-b를 구현할 수 있다!\
i-for문에서 현재의 i에서 다음 i로 증가하기 전, 현재 방향 갱신해준다!

1. 현재 위치 청소\
   \=>**재귀함수 앞쪽에서 조건(Map\[x]\[y]==0) 검사 후 연산 처리(Map\[x]\[y]=2,cnt++)⭐️**
2. 왼쪽 방향부터 차례대로 탐색 =>**반시계 방향 탐색⭐️**\
   왼쪽 방향에 청소할 공간 없으면 다시 2번으로 돌아간다.⭐\
   \= 왼쪽 방향으로 갱신하고, 다시 왼쪽 방향부터 탐색&청소\
   \=> **i-for문으로 4가지 방향에 대해 반복**해주고, **i가 증가하기 전마다 방향 왼쪽으로 갱신**한다!⭐️
3. 네 방향 모두 청소되있거나 벽인 경우, (벽이 아니면)뒤로 한칸 후진\
   \=>i-for문으로 사실상 모든 인접 칸들 탐색&청소한 후 재귀호출한 함수 내에서 더이상 탐색&청소하지 않았기 때문에 flag는 false로 남아있다.//아래 그림의 go(1,0,2)⭐️\
   i-for문 밑의 **if(!flag)문** 조건 만족하여 **뒤로 1칸 후진 실행**한다. 그리고 **if(!flag) 문 내에서 한칸 후진한 위치로 재귀함수 호출**한다. **이 때 이미 4방 모두 청소했거나 벽이기 때문에 아무것도 실행하지 않고 리턴된다!(go(0,0,2)** 리턴되고 난 후 재귀함수에서는 함수내에서 모든 것들을 실행했기 때문에 **본격적으로 호출된 재귀함수들이 역순으로 리턴된다!!!**&#x20;

시뮬레이션 도식화

![](/files/-MgizMBov1PsjQFgU-5O)

![모든 재귀함수들이 역순으로 종료 & 리턴되는 순서](/files/-MgizReAUWSyBulKV2Z8)

\
잘한 부분

1. 재귀함수로 생각해냄.
2. 무엇을 중심으로 생각하고 풀어야할지 생각함. - 현재 위치와 현재 방향.

다른 부분

1. 흔나 : solve(int x,int y,int d,int cnt) : 현재 위치 (x,y) 현재 방향(d)에서 청소를 하는 것이라면\
   Map\[x]\[y] = 2라고만 되어있지만\
   정답 코드 : 현재위치가 청소할 수 있는지 조건판단=>재귀함수 호출할 때 한번 하고, 재귀함수 내, 앞부분에서 한번 더 했다.

   &#x20;if(Map\[x]\[y] == 0){ Map\[x]\[y] = 2; cnt++;}

```
package ss;
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class RobotVacuum_Recursion {
	static int N,M,Map[][],Rx,Ry,Rd;//N:행,M:열, 로봇현재위치 rx,ry,rx
	static int solve(int x,int y,int d,int cnt) {
		Map[x][y] = 2;
		//2
		//2-a
		//2-b
		if(d==0) {
			d=3;
			if(Map[x][y-1] ==0) {
				solve(x,y-1,2,cnt+1);
			} else {solve(x,y,2,cnt);}
		}
		else if(d==1) {//현재 동. 왼쪽 방향전환:북. 1칸 이동 시 x-1,y
			d = 0;
			if(Map[x-1][y]==0) {
				solve(x-1,y,0,cnt+1);
			} else {solve(x,y,0,cnt);}
		}
		else if(d==2) {//현재 남. 왼쪽 방향전환:동. 1칸 이동 시 x,y+1
			d = 1;
			if(Map[x][y+1]==0) {
				solve(x,y+1,1,cnt+1);
			} else {solve(x,y,1,cnt);}
		} else if(d==3) {//현재 서. 왼쪽 방향전환:남. 1칸 이동 시 x+1,y
			d = 2;
			if(Map[x+1][y]==0) {
				solve(x+1,y,2,cnt+1);
			} else {solve(x,y,2,cnt);
		}
			
		//2-c,2-d
		if(d==0) {
			if(Map[x+1][y]==0) {
				solve(x+1,y,d,cnt+1);
			} else {//Map[x+1][y] != 0 후진 못하는 경우.
				return 0;
			}
		}
		else if(d==1) {
			if(Map[x][y-1]==0) {
				solve(x,y-1,d,cnt+1);
			} else {return 0;}
		}
		else if(d==2) {
			if(Map[x-1][y]==0) {
				solve(x-1,y,d,cnt+1);
			} else {return 0;}
		}
		else if(d==3) {
			if(Map[x][y+1]==0) {
				solve(x,y+1,d,cnt+1);
			} else {return 0;}
		}
		
	}
		return cnt;
	}
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] input = br.readLine().split(" ");
		N = Integer.parseInt(input[0]);
		M = Integer.parseInt(input[1]);
		Map = new int[N][M];
		
		input = br.readLine().split(" ");
		Rx = Integer.parseInt(input[0]);
		Ry = Integer.parseInt(input[1]);
		Rd = Integer.parseInt(input[2]);
	
		for(int i=0;i<N;i++) {
			input = br.readLine().split(" ");
			for(int j=0;j<M;j++) {
				Map[i][j] = Integer.parseInt(input[j]);
			}
		}
		//1.현재 위치 청소!2로 마킹!
		Map[Rx][Ry] = 2;
		System.out.println(solve(Rx,Ry,Rd,0));
		br.close();
	}
}
//System.out.println("Rx: "+Rx);
//System.out.println("Ry: "+Ry);
//System.out.println("Rd: "+Rd);
//for(int i=0;i<N;i++) {
//	for(int j=0;j<M;j++) {
//		System.out.print(Map[i][j]+" ");
//	}
//	System.out.println();
//}

```