백준 14503번 로봇 청소기 C++

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

 

방향에 따라 회전하는 것을 잘 구현하는 게 이 문제의 핵심인 것 같다.

위, 오른쪽, 아래, 왼쪽을 바라보는 것이 순서대로 0, 1, 2, 3 이기 때문에 다음 위치를 계산할 수 있게 해주는 배열을

왼쪽, 위, 오른쪽, 아래 순으로 만들었다. 현재 방향이 위쪽, 즉 0이라면 (r + posR[0] , r + posC[0]) 을 해주면 현재 위치와 방향을 기준으로 해서 왼쪽 좌표를 구할 수 있다.

 

그리고 문제에서 1번, 2번 행동이 나뉘어져 있기 때문에 함수에서도 매개변수로 step을 받아서 그에 맞는 코드를 실행시키도록 만들었다.

 

2번의 a에서 위의 식을 이용하면 왼쪽 좌표를 구할 수 있다. 그리고 왼쪽으로 방향도 돌려야 하는데, 하나씩 써보면서 하면 방법을 생각하기 쉽다. 0 -> 3, 1 -> 0, 2 -> 1, 3 -> 2 로 방향이 바뀌어야 하기 때문에 (d+3) % 4를 해주면 된다.

 

2번의 b에서는 회전만 시켜주고 주변의 청소할 수 없는 좌표의 수를 저장하는 cnt를 1 증가시킨다.

2번의 b가 계속되면서 cnt가 4가 됐을때는 4방향 모두 청소를 할 수 없는 상태이기 때문에 현재 좌표의 뒤를 검사해서 갈 수 있다면 후진하고, 갈 수 없다면 함수를 종료한다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>

using namespace std;
typedef long long ll;

int posR[4] = { 0,-1,0,1 };
int posC[4] = { -1,0,1,0 };

int n, m;
int r, c, d;
vector<vector<int>> v(50, vector<int>(50));
int ans = 0;

void Clean(int step, int cnt) {
	if (step == 1) {
		v[r][c] = 2;
		ans++;
		Clean(2, 0);
	}
	else if (step == 2) {
		int leftRow = r + posR[d];
		int leftCol = c + posC[d];
		if (v[leftRow][leftCol] == 0) {
			d = (d + 3) % 4;
			r = leftRow;
			c = leftCol;
			Clean(1, 0);
		}
		else {
			if (cnt < 4) {
				d = (d + 3) % 4;
				Clean(2, cnt + 1);
			}
			else {
				int backRow = r + posR[(d + 3) % 4];
				int backCol = c + posC[(d + 3) % 4];
				if (v[backRow][backCol] == 2) {
					r = backRow;
					c = backCol;
					Clean(2, 0);
				}
				else {
					return;
				}
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n >> m;
	cin >> r >> c >> d;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> v[i][j];
		}
	}
	Clean(1, 0);
	cout << ans;
};