[14503] 로봇 청소기

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

14503번: 로봇 청소기

문제

입력

출력

로봇 청소기가 작동을 시작한 후 작동을 멈출 때까지 청소하는 칸의 개수를 출력한다.

코드

#include <algorithm>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <vector>

using namespace std;

int N, M;
int r, c, d;
int adj[51][51];
int dir[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; //0 1 2 3
int ans = 0;
bool isZero = false;
bool visited[51][51];

void dfs(int x, int y){
	
	isZero = false;
	// 1번
	if(adj[x][y] == 0 && !visited[x][y]){
		visited[x][y] = true;
		ans++;
	}

	//3번
	for(int i=0; i<4; ++i){
		int d2 = (d + 3 - i) % 4;
		int nx = x + dir[d2][0];
		int ny = y + dir[d2][1];

		if(nx < 0 || nx >= N){
			continue;
		}

		if(ny <0 || ny >= M){
			continue;
		}
		
		if(adj[nx][ny] == 0 && !visited[nx][ny]){
			d = d2;
			dfs(nx, ny);
			isZero = true;
			break;
		}
	}

	if(!isZero){
		// 2번
		int d2 = (d+2) % 4;
		int nx = dir[d2][0] + x;
		int ny = dir[d2][1] + y;

		if(nx >= 0 && nx < N && ny >= 0 && ny < M && adj[nx][ny] == 0){
			dfs(nx, ny);
		}
		else{
			return;
		}
	}
}

int main(void){
	cin >> N >> M;
	cin >> r >> c >> d;

	memset(visited, false, sizeof(visited));
	for(int i=0; i<N; ++i){
		for(int j=0; j<M; ++j){
			cin >> adj[i][j];
		}
	}  

	dfs(r, c);

	cout << ans;
}

케이스들을 잘 쪼개면 풀 수 있는 문제이다.

이 때, 문제를 잘 읽어봐야 할게 만약 칸의 값이 1이면 청소 된 상태가 아닌 벽이라는 뜻으로 청소 된 상태를 확인해주는 visited 배열을 하나 더 선언해야 한다. (이걸 잘 못읽어서 좀 많이 헤맸다...)

그리고 주목해야할 점이 방향이 반시계 방향으로 90도 가는 점이나 후진하는 점인데  이 방향들을 %연산자를 사용해 잘  해결해 주었다.

 

1. int d2 = (d + 3 - i) % 4; (반시계 방향으로 90도)

2. int d2 = (d+2) % 4; (바라보는 방향의 반대 방향)