14503 로봇 청소기

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

14503번: 로봇 청소기

(풀이)

문제의 요구 사항

1. 현재 위치를 청소한다.

 

2. 현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다.

  a. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고

     1번부터 진행한다.   

  b. 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.

  c. 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는,

     바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.

  d. 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는

     경우에는 작동을 멈춘다.

 

(풀이) 로봇의 위치 x,y와 바라보는 방향 dir 이 필요하다. for(int i=0; i<4;++i) 문을 이용하여

4방향으로 왼쪽으로 회전을 구현. (a,b)

 

(c)"네 방향 모두 청소가 이미 되어있거나, 벽인 경우 " (for 문을 다 순회한경우)

이 경우는 로봇이 더이상 이동하지 못한경우 이다.

뒤로 후진을 하기위해 dir 변수에 +2칸 dx[] , dy[]의 인덱스로 사용 4방향이므로 mod4 모듈러

연산을 이용하여 0~3 까지 유지시켜줌.

 

후진을 할때에는 현재위치 cur_x ,cur_y에서 후진을 하여야한다.

 

(d)의 조건은 더이상 로봇이 움직이지 못하고 청소도 못하는 상황 이므로 종료.

 

bf 또는와 dfs로 구현 가능. arr의 행렬 제한은 50*50 = O(N^2)에 충분히 들어온다.

 

#include<iostream>
#include<queue>
using namespace std;

int arr[50][50];
int check[50][50];
int N, M;
queue<pair<pair<int, int>,int>> q;
void bfs();
void dfs(int x, int y, int dir);
int dx[] = { -1,0,1,0 };
int dy[] = { 0,1,0,-1 };
int ans = 0;
int main(void)
{
	cin >> N >> M;
	
	int pos_x, pos_y, dir;
	cin >> pos_x >> pos_y >> dir;
	q.push(make_pair(make_pair(pos_x, pos_y), dir));
	ans += 1;
	check[pos_x][pos_y] = true;

	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < M; ++j)
			cin >> arr[i][j];
	}
	//bfs();
	dfs(pos_x, pos_y, dir);



	cout << ans << '\n';
	return 0;
}
void dfs(int x, int y, int dir)
{
	int cur_x = x;
	int cur_y = y;
	//int cur_dir = dir;
	check[cur_x][cur_y] = true;
	int next_dir = dir;
	bool isBack = false;
	for (int i = 0; i < 4; ++i) //a,b
	{
		next_dir = next_dir - 1;
		if (next_dir < 0) next_dir = 3;

		int xn = cur_x + dx[next_dir];
		int yn = cur_y + dy[next_dir];

		if (xn < 0 || xn >= N || yn < 0 || yn >= M) continue;

		if (arr[xn][yn] == 0 && check[xn][yn] == 0) 
		{
			 //a
			ans += 1;
			isBack = true;
			dfs(xn, yn, next_dir);
			break;
		}
	}

	if (isBack == false)
	{
		int new_dir = next_dir + 2;
		new_dir = new_dir % 4;

		int new_xn = cur_x + dx[new_dir];
		int new_yn = cur_y + dy[new_dir];

		if (new_xn >= 0 || new_xn < N || new_yn >= 0 || new_yn < M)
		{
			if (arr[new_xn][new_yn] != 1)
			{
				dfs(new_xn, new_yn, next_dir);
			}
		}

	}

}
void bfs()
{
	while (!q.empty())
	{
		int cur_x = q.front().first.first;
		int cur_y = q.front().first.second;
		int cur_dir = q.front().second;
		
		int next_dir = cur_dir;
		int xn = 0;
		int yn = 0;
		q.pop();
		bool isBack = false;
		for (int i = 0; i < 4; ++i)
		{
			next_dir = next_dir - 1;
			if (next_dir < 0) next_dir = 3; //a. 방향 회전.

			xn = cur_x + dx[next_dir];
			yn = cur_y + dy[next_dir]; // a. 다음칸 지정 
			
			if (xn < 0 || xn >= N || yn < 0 || yn >= M) continue;

			if (arr[xn][yn] == 0 && check[xn][yn] == false)
			{
					check[xn][yn] = true;
					q.push(make_pair(make_pair(xn, yn), next_dir)); //다음칸 전진
					isBack = true;
					break; //1번부터 진행
			}
		}
		if (isBack == false)
		{
			// c번 
				//뒤로 한칸 후진.
				int new_move = next_dir + 2;
				new_move = new_move % 4;
				xn = cur_x + dx[new_move];
				yn = cur_y + dy[new_move];
				if (xn < 0 || xn >= N || yn < 0 || yn >= M) continue;
				
				if (arr[xn][yn] != 1)
				{
					q.push(make_pair(make_pair(xn, yn), next_dir));
				}
		
		}
	}
}