백준 14503 (로봇 청소기)

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

14503번: 로봇 청소기

 

해당 문제는 재귀를 이용하여 지문의 조건에 맞게 풀었다.

지문의 조건을 요약하면 다음과 같다

1. 청소기의 현재 방향을 기준으로 왼쪽이 청소를 하지 않은 영역이라면 해당 영역을 청소하고 청소기의 방향전환

2. 만약 청소기의 왼쪽 영역이 청소가 되어 있거나 벽이라면 청소기의 방향을 왼쪽으로 돌린 뒤 다시 1 부터 수행

3. 만약 청소기를 계속 왼쪽 방향으로 돌려 4방위를 모두 탐색했을 때 모든 방향이 청소가 되어있거나 벽이라면 왔었던 곳으로 후진 한다. 이때 방향은 왔던 방향을 유지하며 후진한다

 

1 2 3 조건을 반복하며 마지막에 후진 했을 때 해당 영역이 벽이라면 청소를 종료하고 청소한 영역의 개수를 반환한다.

풀이

재귀함수를 이용하여 풀었으며 재귀를 하는 경우는 2가지 이다.

첫번째는 현재 위치를 기준으로 왼쪽 방향이 비었을 때 또는 왼쪽 방향이 아닌 다른 방향이 비었을 때 재귀를 수행

두번째는 현재 위치를 기준으로 모든 방향이 벽 또는 청소를 수행한 영역일 때 재귀를 수행한다. 이때에는 이전 영역의 좌표를 매개변수로 넘겨주며 방향은 현재 방향을 그대로 넘겨준다.

첫번째 재귀시 주의할 점이 한가지 있는데 반드시 4방향중 한 군데라고 청소가 가능하다면 재귀를 수행한 뒤 반환 되었을 때 해당 함수를 바로 반환해주어야 한다. 만약 바로 반환해주지 않는다면 해당 함수는 남은 방향을 다시 모두 탐색하게 되고 이는 조건과 일치하지 않게 된다.

즉 현재 위치에서 왼쪽 그리고 왼쪽이 청소 혹은 벽일 경우 남은 방향을 탐색한 경우를 재귀하며 해당 경우의 수를 구한 뒤 return, 모든 방향이 막혔을 때 방향은 그대로 유지하며 후진하여 1 2 를 다시 수행하면 된다. 이와 같은 과정을 반복하면 결국 후진했을 때 벽에 도달하는 경우가 발생하게 되고 벽에 도달 했을때 재귀를 종료시키면 된다.

소스

#include <iostream>
#include <cstring>

using namespace std;
int my, mx;
int map[50][50];
int visit[50][50];

int dirList[4][2] = {
	-1, 0,
	0, +1,
	+1, 0,
	0, -1
};

// 현재 좌표를 기준으로 왼쪽 방향을 반환한다.
int getDir(int dir){
	if (dir == 0){
		return 3;
	}
	if (dir == 1){
		return 0;
	}
	if (dir == 2){
		return 1;
	}
	if (dir == 3){
		return 2;
	}
}


void dfs(int y, int x, int dir){
	// 만약 현재 위치가 가장자리라면 반환
	if (y < 1 || x < 1 || y >= my - 1 || x >= mx - 1 ){
		return;
	}
    // 만약 가장자리는 아니지만 현재 위치가 벽이라면 반환
	if (map[y][x] == 1){
		return;
	}

	int tmpDir = dir;

	// 왼쪽 또는 왼쪽을 제외한 남은 방향중 청소하지 않은 영역 탐색
	for (int i = 0; i < 4; ++i){
		tmpDir = getDir(tmpDir);
		int dy = y + dirList[tmpDir][0];
		int dx = x + dirList[tmpDir][1];
		if (dy >= 1  && dx >= 1 && dy <= my - 2 && dx <= mx - 2 && visit[dy][dx] == 0){
			visit[dy][dx] = 2;
			dfs(dy, dx, tmpDir);
            // 만약 이때 반환 하지 않는다면 주어진 MAP의 빈 곳을 전부 탐색하게 된다.
            return;
		}
	}
	int dy = 0;
	int dx = 0;

	// 위에서 4방향이 전부 청소가 되어있거나 벽이라면 후진하는 코드
	if (dir == 0){
		dy = y + dirList[2][0];
		dx = x + dirList[2][1];
	}
	else if (dir == 1){
		dy = y + dirList[3][0];
		dx = x + dirList[3][1];
	}
	else if (dir == 2){
		dy = y + dirList[0][0];
		dx = x + dirList[0][1];
	}
	else if (dir == 3){
		dy = y + dirList[1][0];
		dx = x + dirList[1][1];
	}
	dfs(dy, dx, dir);
}

int main(){
	//freopen_s(new FILE*, "tes.text", "r", stdin);
	int sy, sx, dir;

	cin >> my >> mx;
	cin >> sy >> sx >> dir;

	for (int i = 0; i < my; ++i){
		for (int j = 0; j < mx; ++j){
			cin >> map[i][j];
		}
	}
	memcpy(visit, map, 4 * 50 * 50);
	visit[sy][sx] = 2;
	dfs(sy, sx, dir);

	int cnt = 0;
	for (int i = 0; i < my; ++i){
		for (int j = 0; j < mx; ++j){
			if (visit[i][j] == 2) ++cnt;
		}
	}
	printf("%d", cnt);
}