백준 14053번: 로봇 청소기 - 시뮬레이션 문제 C++

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

14503번: 로봇 청소기

1.문제설명

d가 0인 경우에는 북쪽을, 1인 경우에는 동쪽을, 2인 경우에는 남쪽을, 3인 경우 서쪽을 나타낸다.

 

로봇 청소기는 다음과 같이 작동한다.

1. 현재 위치를 청소한다.
2. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향부터 차례대로 인접한 칸을 탐색한다.
   1. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.
   2. 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.
   3. 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.
   4. 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.

방향을 전환하면서 이동하면서 청소를 할 수 있는 방의 개수를 찾아야 하는 문제다.

 

 

2.접근 방법[알고리즘]

이 문제를 DFS를 통해 시뮬레이션을 할 때 

종료 조건은 탐색할 수 있는 네 방향 모두 이미 청소되었거나 벽인 경우이고 후진을 할 수 없을 때다.

 

DFS를 돌면서 네방향 모두 체크해주고,

네방향 모두 이미 청소되었거나 벽이라면 

후진을 시켜주고 후진을 할 수 없다면 종료를 시켜준다.

 

종료조건에 해당하지 않는다면

방향전환을 하고, 방향전환시 전진 했을 때 청소가 가능한 방이라면 전진을 시켜준다.

청소가 불가능 한 방이라면 전진하지 않는다.

 

해당 좌표가 이미 방문했던 점이라도 다시 방문해도 상관 없다

위 조건에만 만족하면 된다.

 

DFS코드

void DFS(int x, int y, int d) {
	if (ended) return;
	bool all_cleaned = true;

	//네방향 확인 
	for (int i = 0; i < 4; i++) {
		if (arr[x + dx[i]][y + dy[i]] == 0) {
			all_cleaned = false;
			break;
		}
	}
	if (all_cleaned) {
		// 벽이 있어서 후진 할 수 없다면 종료
		if (arr[x - dx[d]][y - dy[d]] == -1) {
			ended = true;
			return;
		}
		else {
			//후진이 가능할 때
			DFS(x - dx[d], y - dy[d], d);
		}
	}
	// 왼쪽으로 방향 회전 
	int nd = d == 0 ? 3 : d - 1;
	int nx = x + dx[nd];
	int ny = y + dy[nd];

	if (arr[nx][ny] == 0) {
		arr[nx][ny] = ++cleaned;
        //청소 가능한 방이라면 방향전환후 전진
		DFS(nx, ny, nd);
	}
	else {
    	//청소 불가능한 방이라면 방향전환만 
		DFS(x, y, nd);
	}
}

 

 

3.문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;

int n, m, r, c, d, arr[51][51], cleaned;
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };
bool ended = false;

void DFS(int x, int y, int d) {
	if (ended) return;
	bool all_cleaned = true;

	//네방향 확인 
	for (int i = 0; i < 4; i++) {
		if (arr[x + dx[i]][y + dy[i]] == 0) {
			all_cleaned = false;
			break;
		}
	}
	if (all_cleaned) {
		// 벽이 있어서 후진 할 수 없다면 종료
		if (arr[x - dx[d]][y - dy[d]] == -1) {
			ended = true;
			return;
		}
		else {
			//후진이 가능할 때
			DFS(x - dx[d], y - dy[d], d);
		}
	}
	// 왼쪽으로 방향 회전 
	int nd = d == 0 ? 3 : d - 1;
	int nx = x + dx[nd];
	int ny = y + dy[nd];

	if (arr[nx][ny] == 0) {
		arr[nx][ny] = ++cleaned;
		DFS(nx, ny, nd);
	}
	else {
		DFS(x, y, nd);
	}
}


int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	cin >> r >> c >> d;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> arr[i][j];
			if (arr[i][j] == 1) {
				arr[i][j] = -1;
			}
		}
	}
	arr[r][c] = ++cleaned;
	DFS(r, c, d);
	cout << cleaned;
	return 0;
}

백준 14503번 메모리 및 시간