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

문제

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

14503번: 로봇 청소기

 

문제풀이

현재 위치에서 바라보는 방향 기준 왼쪽부터 반시계 방향으로 돌면서 청소할 칸을 확인한다.

청소할 칸이 있으면 청소할 칸 쪽으로 회전을 한 뒤 한 칸 이동한다.

벽이거나 청소할 칸이 없으면 다시 회전을 한다.

네 방향을 탐색했으면 90도의 회전이 총 네 번 있었으므로 방향이 처음 방에 들어온 상태로 된다.

뒷 칸이 벽이면 작동을 멈춘다. 뒷 칸이 벽이 아니면 뒤로 한 칸 이동한다.

 

vector<int>robot(3,0);
vector<vector<int>>Arr;
vector<pair<int, int>>loc = { { 0,-1 }, {1, 0}, {0, 1}, {-1, 0}  };

	cin >> robot[0] >> robot[1] >> robot[2];
	robot[2] = (4 - robot[2]) % 4;

robot벡터는 현재 로봇의 상태를 나타낸다. { y좌표, x좌표, 바라보는 방향}이다.

Arr은 칸의 상태들을 나타내는 2차원 벡터.

바라보는 방향 기준 왼쪽 칸을 탐색하므로

loc벡터는 현재 칸 기준 서쪽, 남쪽, 동쪽, 북쪽 방향 순으로 (반시계 방향) 나열했다.

문제에서는 0: 북쪽, 1: 동쪽을, 2: 남쪽, 3: 서쪽 이기 때문에 좀 헷갈릴 수도 있다.

처음 입력받을 때 한 번만 (4 - 입력값)%4를 하여 문제에 나온 대로 설정해준다.

 

void Clean() {
	if (Arr[robot[0]][robot[1]] == 0) clean_cnt++;
	Arr[robot[0]][robot[1]] = 2;

	while (1) {
		int dir = robot[2];
		int cnt = 0;
		for (cnt = 0; cnt < 4; ++cnt) {
			dir = robot[2];
			int n_y = robot[0] + loc[dir].first;
			int n_x = robot[1] + loc[dir].second;
			if (n_y >= 0 && n_y < N && n_x >= 0 && n_x < M) {
				if (Arr[n_y][n_x] == 0) {
					Arr[n_y][n_x] = 2;
					robot[0] = n_y;
					robot[1] = n_x;
					robot[2] = (dir + 1) % 4;
					clean_cnt++;
					break;
				}
				else {
					robot[2] = (dir + 1) % 4;
				}
			}
		}
		if (cnt == 4) {
			robot[0] += loc[(dir + 2) % 4].first;
			robot[1] += loc[(dir + 2) % 4].second;
			if (Arr[robot[0]][robot[1]] == 1)
				return;
		}
	}
}

총 네 방향을 봐야 탐색해 야하므로 탐색하는 새로운 y, x좌표들을 현재 로봇 위치 + loc벡터를 이용하여 네 방향을 탐색할 수 있게 한다.

청소할 수 있는 칸이 있으면 청소를 한다.

여기서는 청소한 칸을 2로 두어 다시 방문할 수는 있지만 다시 청소할 수 없게 한다.

그리고 그 칸으로 가야 하기 때문에 한 번만 실행한다.

만약 네 방향 모두 청소를 할 수 없으면 (cnt가 4일 때), 네 번 회전했으므로 현재 칸에 처음 들어왔을 때 상태이다.

그러므로 2번 회전한 (dir+2) 값은 로봇 한 칸 뒤 이므로 로봇의 값을 한 칸 후진한 칸으로 바꿔준다.

만약 한 칸 뒤가 벽이라면 로봇 작동을 멈춘다.

 

 

코드

#include <iostream>
#include <vector>
using namespace std;

int N, M;
vector<int>robot(3,0);
vector<vector<int>>Arr;
vector<pair<int, int>>loc = { { 0,-1 }, {1, 0}, {0, 1}, {-1, 0}  };
int clean_cnt;

void Clean() {
	if (Arr[robot[0]][robot[1]] == 0) clean_cnt++;
	Arr[robot[0]][robot[1]] = 2;

	while (1) {
		int dir = robot[2];
		int cnt = 0;
		for (cnt = 0; cnt < 4; ++cnt) {
			dir = robot[2];
			int n_y = robot[0] + loc[dir].first;
			int n_x = robot[1] + loc[dir].second;
			if (n_y >= 0 && n_y < N && n_x >= 0 && n_x < M) {
				if (Arr[n_y][n_x] == 0) {
					Arr[n_y][n_x] = 2;
					robot[0] = n_y;
					robot[1] = n_x;
					robot[2] = (dir + 1) % 4;
					clean_cnt++;
					break;
				}
				else {
					robot[2] = (dir + 1) % 4;
				}
			}
		}
		if (cnt == 4) {
			robot[0] += loc[(dir + 2) % 4].first;
			robot[1] += loc[(dir + 2) % 4].second;
			if (Arr[robot[0]][robot[1]] == 1)
				return;
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int y = 0, x = 0;
	cin >> N >> M;
	cin >> robot[0] >> robot[1] >> robot[2];
	Arr = vector<vector<int>>(N, vector<int>(M, 0));
	
	robot[2] = (4 - robot[2]) % 4;	

	for (y = 0; y < N; ++y) {
		for (x = 0; x < M; ++x) {
			cin >> Arr[y][x];
		}
	}
	Clean();
	cout << clean_cnt;
}