[삼성코테기출문제] 로봇청소기

로봇청소기

문제

다른 문제들에 비하면 많이 까다롭지 않은 문제였다. 조심해야 할 부분은 로봇청소기가 바라보는 방향이 있고, 모든 방향이 청소가 되었다면 후진을 한다. 이에 대한 처리를 좀 잘 생각해야했다.

문제 풀이

입출력 조건

로봇이 움직이므로 로봇의 좌표를 큐에 넣어준다. 이 때 로봇은 바라보는 방향이 있으므로 방향도 같이 큐에 넣어준다.

풀이 과정

1. 맵의 정보를 입력받고, 로봇의 좌표와 방향도 입력받아 큐에 넣어준다.
2. 현재 로봇위치를 pop하여 받고 그 위치를 청소했다는 표시로 Map[cury][curx] = 2를 해준다. 그리고 한 구역을 청소 했으므로 Answer++
3. 4방향을 탐색할 때 로봇은 바라보는 방향을 가지고 있으므로

    //D:북(0),동(1),남(2),서(3)
    int dx[4] = { 0,1,0,-1 };
    int dy[4] = { -1,0,1,0 };
   
    int nd = (cur.d + (3 - i)) % 4;  
   
   

   이와 같이 처리해 준다.
   만약 바라보는 방향이 북쪽(0)이라면 위의 계산식의 결과는 0 + 3,2,1,0 순이 된다. 따라서 서(3), 남(2), 동(1), 북(0) 순으로 탐색할 수 있다.

4. 4방향을 모두 청소하였는지를 확인하기위한 bool flag를 false하고 4방향의 이동 유무를 확인한다.
   4방향을 모두 확인하고 나서 만약 flag=false라면 주변이 벽이거나 이미 청소를 했던 곳이다. 따라서 로봇을 후진하여 해당 좌표와 뱡항을 push해준다.
5. 이 과정을 반복하여 수행하고 로봇이 청소한 구역을 모두 계산한다.

#include<iostream>

using namespace std;

const int MAX = 50;
int N, M, Answer;
int Map[MAX][MAX];
//D:북(0),동(1),남(2),서(3)
int dx[4] = { 0,1,0,-1 };
int dy[4] = { -1,0,1,0 };
typedef struct Pos {
	int x, y;
	int d;
};

Pos Q[MAX*MAX]; int f, r;
void push(int x, int y,int d) {
	Q[r++] = { x,y,d };
}
Pos pop() {
	return Q[f++];
}

void Input() {
	cin >> N >> M;
	int r, c, d;
	cin >> r >> c >> d;
	push(c, r, d);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> Map[i][j];
		}
	}
}
void Process() {
	while (f != r) {
		Pos cur = pop();
		if (Map[cur.y][cur.x] == 0) {
			Map[cur.y][cur.x] = 2;
			Answer++;
		}

		bool flag = false;
		for (int i = 0; i < 4; i++) {
			int nd = (cur.d + (3 - i)) % 4;
			int nx = cur.x + dx[nd];
			int ny = cur.y + dy[nd];
			if (ny >= 0 && nx >= 0 && ny < N&&nx < M) {
				if (!Map[ny][nx]) {
					push(nx, ny, nd);
					flag = true;
					break;
				}
			}
		}
		if (!flag) {
			//before
			int bx = cur.x - dx[cur.d];
			int by = cur.y - dy[cur.d];
			if ((by >= 0 && bx >= 0 && by < N&&bx < M) && Map[by][bx] != 1)
				push(bx, by, cur.d);
			else break;
		}
	}
}
void Solution() {
	Input();
	Process();
	cout << Answer << "\n";
}
int main() {
	freopen("09.in", "r", stdin);
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	Solution();
	return 0;
}