로봇 청소기

문제의 핵심 : 현재 위치와 방향이 계속 변화하고, 왼쪽 방향 먼저 탐색(&청소)한다! 델타어레이로 왼쪽 방향, 뒤쪽 방향 전환 시 변화하는 방향 일반화⭐️⭐️⭐️⭐️⭐️ 현재 방향을 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) 리턴되고 난 후 재귀함수에서는 함수내에서 모든 것들을 실행했기 때문에 본격적으로 호출된 재귀함수들이 역순으로 리턴된다!!!

시뮬레이션 도식화

모든 재귀함수들이 역순으로 종료 & 리턴되는 순서

잘한 부분

1. 재귀함수로 생각해냄.

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

다른 부분

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

   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();
//}