# 로봇 청소기

문제의 핵심 : 현재 위치와 방향이 계속 변화하고, 왼쪽 방향 먼저 탐색(&청소)한다!\
델타어레이로 왼쪽 방향, 뒤쪽 방향 전환 시 변화하는 방향 일반화⭐️⭐️⭐️⭐️⭐️\
현재 방향을 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();
//}

```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://heunnajo.gitbook.io/algorithms-problem-solving-skills/undefined-1/undefined-12.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.