[백준 14503] 로봇 청소기 cpp

문제
로봇 청소기가 청소하는 영역의 개수 구하기
로봇 청소기가 이동할 수 있는 맵은 NxM 크기의 직사각형이고 각각의 칸은 벽 또는 빈 칸이다.
청소기는 바라보는 방향이 있고 상하좌우로 이동할 수 있다.

로봇 청소기는 다음과 같이 동작한다.
1. 현재 위치를 청소한다.
2. 현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색 진행
2-1. 왼쪽 방향에 청소할 공간이 있으면 그 방향으로 회전한 다음 한 칸 전진후 1번부터 진행
2-2. 왼쪽 방향에 청소할 공간이 없다면 그 방향으로 회전 후 2번으로 돌아간다.
2-3. 네 방향 모두 청소가 되었거나 벽인 경우네는 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.
2-4. 네 방향 모두 청소가 되었거나 벽이면서 뒤쪽 방향이 벽이라 후진도 할 수 없으면 멈춘다.

이미 청소한 공간은 또 청소하지 않고 벽을 통과할 수 없다.

입력
첫째 줄에 세로 크기 N, 가로 크기 M이 주어진다. 
(3이상 50이하)
둘째 줄에 청소기가 있는 좌표와 바라보는 방향 D가 주어진다.
D가 0: 북 1: 동 2: 남 3: 서
셋째 줄부터 맵의 정보가 주어지고 빈 칸은 0 벽은 1이다.
로봇 청소기가 있는 칸의 상태는 항상 빈 칸이다.

출력
로봇 청소기가 청소하는 칸의 개수 출력

---

문제에서 주어진 조건으로 로봇 청소기를 이동시켜 청소를 해야한다.

 

먼저 로봇 청소기를 어떻게 이동시켜야하는지에 대한 생각을 하였다. 

로봇은 위치와 방향을 갖고 이동할 때마다 위치와 방향 값이 바뀌게 된다. 따라서 로봇을 구조체로 모델링한다. Robot이라는 구조체에 위치(y, x)와 방향(d)를 포함시킨다.

 

이제 이 Robot으로 탐색하고 이동하는 기능을 구현해야 한다.

기본적으로 탐색은 BFS를 활용한다.

입력으로 방향이 주어질 때 북 동 남 서가 순서대로 0 1 2 3의 값을 갖기때문에 상하좌우로 이동하기 위한 dir값을 북 동 남 서 순서대로 만든다. 

이제 dir을 이용해 현재방향을 기준으로 왼쪽부터 탐색을 해야한다. 예를 들어 현재 방향이 북(0)이라면 3->2->1 순서대로 탐색해야하기 때문에 d:0~3 -> (현재방향 + 3 - d) % 4를 한다.

 

탐색한 곳이 청소해야되는 공간이면 큐에 넣고 반복문을 멈춘다.

반복문이 종료되었을 때도 큐가 비어있으면 사방에 0이 없다는 뜻이므로 현재방향을 기준으로 뒤로 간다.

이때 뒤가 1이라면 BFS를 종료한다.

 

#include "pch.h"
#include <iostream>
#include<algorithm>
#include <vector>
#include<queue>
using namespace std;

struct Robot {
	int y, x;
	int d;
};

int N, M;
int answer;
int map[50][50];
int dir[4][2] = { {-1,0},{0,1},{1,0},{0,-1} };


bool Range(int y, int x) {
	return(y >= 0 && y < N) && (x >= 0 && x < M);
}
int main()
{
	Robot robot;
	cin >> N >> M;
	cin >> robot.y >> robot.x >> robot.d;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> map[i][j];
		}
	}

	queue<Robot> q;
	q.push(robot);

	while (!q.empty()) {
		Robot cur = q.front();
		q.pop();

		if (map[cur.y][cur.x] == 0) {
			map[cur.y][cur.x] = 2;
			answer += 1;
		}

		for (int d = 0; d < 4; d++) {
			Robot next;
			next.d = (cur.d + 3 - d) % 4;
			next.y = cur.y + dir[next.d][0];
			next.x = cur.x + dir[next.d][1];
			if (Range(next.y, next.x) && map[next.y][next.x] == 0) {
				q.push(next);
				break;
			}
		}

		if (q.empty()) {
			Robot next;
			// 현재방향을 유지한 채 뒤로가기
			next.d = cur.d;
			next.y = cur.y + dir[(next.d+2)%4][0];
			next.x = cur.x + dir[(next.d+2)%4][1];
			if (map[next.y][next.x] == 1 || !Range(next.y, next.x))
				break;
			q.push(next);
		}
	}
	cout << answer << endl;
}

 

후기

이 문제는 시뮬레이션으로 분류가 되어있다. 사실 제시된 조건대로 구현만하면 되지만 코드로 어떻게 구현할지 감이 잡히지 않는다. 여러가지 알고리즘을 공부하여 그에 관한 문제를 풀기 전에 구현능력이 바탕이 되어야할 것 같다. 

특히 코드로 구현하기 위해 로봇 청소기를 어떻게 모델링하고 해당 기능을 어떻게 구현할지 나눠서 생각해보자.