백준 14503 로봇 청소기

https://www.acmicpc.net/problem/14503

문제와 채점은 위 사이트에서 확인 하실 수 있습니다.

 

이 문제는 로봇 청소기가 청소를 할때 몇칸을 청소 하는지를 구하는 문제입니다. 기본적으로 로봇 청소기가 바라보는 방향이 주어지고 로봇 청소기는 그방향을 기준으로 왼쪽으로 방향을 회전하면서 청소를 할 수 있을때 전진하여 청소를 합니다. 청소를 하지 못할경우 뒤가 벽이 아니라면 후진을 하며 계속해서 진행을 하고 후진을 못하면 정지하게 되는 원리로 작동합니다. 따라서 입력받은 기준으로 왼쪽으로 회전시키는 좌표 배열과, 후진할때 좌표를 조절하는 배열을 따로 만들어서 탐색을 해주어야 합니다. 방향이 0부터 시작해서 북 동 남 서 이므로 왼쪽으로 회전하는 것은 인덱스에서 -1씩 가는 것과 동일합니다. 따라서 d-1 ~ d-4 까지의 값을  인덱스로 잡아주면 왼쪽으로 회전 할 수 있습니다. 

 

다음은 코드입니다.

 

#include <iostream>

using namespace std;

//북동남서 
int nextx[4] = {-1, 0, 1, 0};
int nexty[4] = {0, 1, 0, -1};

int backx[4] = {1, 0, -1, 0};
int backy[4] = {0, -1, 0, 1};
int N,M;
int space[51][51];
int num;
bool flag = true;

void dfs(int x, int y, int d) {
	int ci;
	
	if(space[x][y] == 0) {
		num++;
		space[x][y] = 2;
	}
	
	for(int i = d-1; i > d-5; i--) { 
		
		ci = (i+4) % 4;
		
		int xx = x + nextx[ci];
		int yy = y + nexty[ci];
		
		if(xx < 0 || xx > N-1 || yy < 0 || yy > M-1)
			continue;
		
		if(space[xx][yy] == 0) {
			dfs(xx, yy, ci);
			return; 
		}
	}

	if(space[x+backx[d]][y+backy[d]] == 1)
		flag = false; //후진 불가능 
	else if(flag)
		dfs(x+backx[d], y+backy[d], d);
	
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> N >> M;
	int r,c,d;
	cin >> r >> c >> d;
	
	for(int i = 0; i < N; i++)
		for(int j = 0; j < M; j++)
			cin >> space[i][j];
	

	dfs(r, c, d);
	cout<<num;
	return 0;
}