[백준] 14503번 로봇 청소기 - C/C++ (Easy 풀이)

백준 14503 문제(Problem)

백준 14503 문제

풀이 & 전체 코드(Solution & Code)

이 문제는 문제에 작성된 논리대로 코드를 구현하면 된다.

 

로봇 청소기의 움직임)
1. 현재 칸이 아직 청소되지 않은 경우, 현재 칸을 청소한다.

if(!map[y][x]) { // 1. 청소되지 않은 칸이면 청소 표시
	cnt++;
	map[y][x]=2;  // 청소 표시: 2
}

 

2. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 없는 경우,

- 바라보는 방향을 유지한 채로 한 칸 후진 후 1번으로 돌아감

- 바라보는 방향의 뒤쪽 칸이 벽이면 작동을 멈춤

if(check(x, y)) { // 2. 주변의 4칸 중 청소되지 않은 빈칸이 없는 경우
	nd = (d+2)%4;
	nx=x+dx[nd];
	ny=y+dy[nd];
	if(map[ny][nx] == 1) { dis=1; return; }
	func(nx, ny, d);  // 바라보는 방향 유지하면서 후진
}

check 함수는 주변 4칸이 모두 청소가 되어있지 않으면 1을 반환하는 함수이다.

'nd = (d+2) % 4' 를 이용하여 뒤쪽 방향을 쉽게 설정하였고 이를 이용해 nx와 ny의 좌표(뒤쪽 좌표)를 구하였다.

또한, 뒤쪽 좌표가 벽(1)이면 판별 변수 dis를 1로 바꾸어 func함수의 기저 조건을 통해 바로 빠져나오도록 해주고, 아니면 후진하도록 재귀호출하였다.

** 이때 놓칠 수 있는 점이 바라보는 방향을 유지하면서 후진이기 때문에 매개변수로 nd가 아닌 d를 넣어주어야 함.

 

3. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 있는 경우,

- 반시계 방향으로 90도 회전

- 바라보는 방향을 기준으로 앞쪽 칸이 청소되지 않은 빈 빈칸인 경우 한 칸 전진

- 1번으로 돌아감

else {  // 3. 현재 칸의 주변 4칸 중 청소되지 않은 빈칸이 있는 경우
	nd=d;
	for(int i=1; i<=4; i++) {
		nd = (nd+3)%4;
		nx=x+dx[nd];
		ny=y+dy[nd];
		if(!map[ny][nx]) {
			func(nx, ny, nd);
			break;
		}
	}
}

'nd = (nd+3)%4' 를 이용하여 반시계 방향으로 90도 회전하였다.

여기에서 break를 해주는 이유는 func(nx, ny, nd) 함수가 끝나고 그 위치에서 방향을 틀어 또다시 움직 일 수 있는 가능성을 없애기 위함이다. func(nx, ny, nd) 함수가 종료되었다는 것은 로봇청소기가 작동을 멈췄기 때문에 답은 이미 구해진 상태이다. 그래서 break를 통해 바로 종료시켜주어야 한다.

 

 

전체코드

#include<iostream>
using namespace std;
int n, m , r, c, d, map[51][51], cnt, dis, nx, ny, nd;
// 북: 0, 동: 1, 남:2, 서: 3
int dx[] = {0, 1, 0, -1};
int dy[] = {-1, 0, 1, 0};

bool check(int x, int y) {
	for(int i=0; i<4; i++) {
		nx=x+dx[i], ny=y+dy[i];
		if(nx>=0 && nx<m && ny>=0 && ny<n && !map[ny][nx]) return 0;
	}
	return 1;
}

void func(int x, int y, int d) {
	if(dis) return;
	if(map[y][x]==1) { return; }
	if(!map[y][x]) { // 1. 청소되지 않은 칸이면 청소 표시
		cnt++;
		map[y][x]=2;  // 청소 표시: 2
	}

	if(check(x, y)) { // 2. 주변의 4칸 중 청소되지 않은 빈칸이 없는 경우
		nd = (d+2)%4;
		nx=x+dx[nd];
		ny=y+dy[nd];
		if(map[ny][nx] == 1) { dis=1; return; }
		func(nx, ny, d);  // 바라보는 방향 유지하면서 후진
	} else {  // 3. 현재 칸의 주변 4칸 중 청소되지 않은 빈칸이 있는 경우
		nd=d;
		for(int i=1; i<=4; i++) {
			nd = (nd+3)%4;  // 시계 반대방향 90도 회전
			nx=x+dx[nd];
			ny=y+dy[nd];
			if(!map[ny][nx]) {
				func(nx, ny, nd);
				break;
			}
		}
	}
}

int main() {
	cin >> n >> m;
	cin >> r >> c >> d;
	for(int i=0; i<n; i++)
		for(int j=0; j<m; j++)
			cin >> map[i][j];
	func(c, r, d);
	cout << cnt;
}