문제 보기: 로봇 청소기

난이도: 골드 5

알고리즘 분류: 구현, 시뮬레이션

풀이

📌 문제에서 주어진 작동 조건에 따라 차례대로 수행하고, 네 방향 탐색 여부를 flag를 사용해 구분했습니다.

변수

• 방향: 위, 오른쪽, 아래, 왼쪽 순서로 dy와 dx를 정의해 인덱스가 낮아질수록 현재 방향에서 왼쪽으로 회전하도록 합니다.
• 로봇 청소기: 현재 위치 _y,_x와 현재 방향_dir을 가집니다.

const int MAX = 50;
int map[MAX][MAX];

// U R D L
const int dy[4] = {-1,0,1,0};
const int dx[4] = {0,1,0,-1};

int N, M;
int nAnswer;

class RobotCleaner
{
public:
	int _y, _x;
	int _dir;

	RobotCleaner()
		: _y(0), _x(0), _dir(0)
	{}
};
RobotCleaner robotCleaner;

시뮬레이션

• 빈 칸은 0, 벽은 1, 청소를 마친 곳은 2로 나타냅니다.

• 작동을 멈추는 조건에 해당할 때까지 무한루프를 돕니다.

• 조건 1에 따라 현재 위치를 청소합니다. 청소하는 칸의 수 nAnswer를 세어줍니다.

void Solve()
{
	// 0: Empty
	// 1: Wall
	// 2: Cleaned
	
	while (true) {
		int cy = robotCleaner._y;
		int cx = robotCleaner._x;

		// Step 1. Clean Current Location
		if (map[cy][cx] == 0) {
			map[cy][cx] = 2;
			nAnswer++;
		}

		/* ... */
}

• 조건 2에 따라 왼쪽 방향에 청소하지 않은 빈 공간이 나올 때까지 왼쪽으로 돌며 탐색을 계속합니다.

• 최대 4번, 제자리에서 한 바퀴 회전하며 bCleaned flag를 사용해 탐색 성공 여부를 확인합니다.

void Solve()
{
	// 0: Empty
	// 1: Wall
	// 2: Cleaned
	
	while (true) {
		/* ... */
        
		// Step 2. Turn Left
		bool bCleaned = false;
        // 최대 4방향 탐색
		for (int nCnt = 0; nCnt < 4; nCnt++) {
			int curDir = robotCleaner._dir;
			int nextDir = ((--curDir) + 4) % 4;

			int ny = cy + dy[nextDir];
			int nx = cx + dx[nextDir];
			
			if (map[ny][nx] == 0) {
            	// 탐색 성공 시 이동 후 루프 탈출
				robotCleaner._dir = nextDir;
				robotCleaner._y = ny;
				robotCleaner._x = nx;
				bCleaned = true;
				break;
			}
			else if (map[ny][nx] == 1 || map[ny][nx]==2) {
				robotCleaner._dir = nextDir;
				continue;
			}
		}

		/* ... */
}

• 탐색에 실패한 경우 후진을 하거나, 뒤쪽이 벽이라면 멈추고 현재까지 청소한 칸의 개수를 출력합니다.

void Solve()
{
	// 0: Empty
	// 1: Wall
	// 2: Cleaned
	
	while (true) {
		/* ... */

		// After Search 4 directions
        // 탐색에 실패
		if (!bCleaned) {
			// Go back
			int ny = robotCleaner._y - dy[robotCleaner._dir];
			int nx = robotCleaner._x - dx[robotCleaner._dir];
			
            // 뒤가 벽이라면 멈추고
			if (map[ny][nx] == 1)
				break;
			// 아니면 후진합니다.
			else {
				robotCleaner._y = ny;
				robotCleaner._x = nx;
				continue;
			}
		}
	}
	
    // 청소기가 멈춘 경우 답을 출력합니다.
	std::cout << nAnswer << "\n";
}

Source Code

#include <iostream>

const int MAX = 50;
int map[MAX][MAX];

// U R D L
const int dy[4] = {-1,0,1,0};
const int dx[4] = {0,1,0,-1};

int N, M;
int nAnswer;

class RobotCleaner
{
public:
	int _y, _x;
	int _dir;

	RobotCleaner()
		: _y(0), _x(0), _dir(0)
	{}
};
RobotCleaner robotCleaner;

void Solve();

int main()
{
	// IO Setting
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	// INPUT
	std::cin >> N >> M;
	std::cin >> robotCleaner._y >> robotCleaner._x >> robotCleaner._dir;
	
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < M; x++) {
			std::cin >> map[y][x];
		}
	}

	Solve();

	return 0;
}

void Solve()
{
	// 0: Empty
	// 1: Wall
	// 2: Cleaned
	
	while (true) {
		int cy = robotCleaner._y;
		int cx = robotCleaner._x;

		// Step 1. Clean Current Location
		if (map[cy][cx] == 0) {
			map[cy][cx] = 2;
			nAnswer++;
		}

		// Step 2. Turn Left
		bool bCleaned = false;
		// 최대 4방향 탐색
		for (int nCnt = 0; nCnt < 4; nCnt++) {
			int curDir = robotCleaner._dir;
			int nextDir = ((--curDir) + 4) % 4;

			int ny = cy + dy[nextDir];
			int nx = cx + dx[nextDir];
			
			if (map[ny][nx] == 0) {
				// 탐색 성공 시 이동 후 루프 탈출
				robotCleaner._dir = nextDir;
				robotCleaner._y = ny;
				robotCleaner._x = nx;
				bCleaned = true;
				break;
			}
			else if (map[ny][nx] == 1 || map[ny][nx]==2) {
				robotCleaner._dir = nextDir;
				continue;
			}
		}

		// After Search 4 directions
		// 탐색에 실패
		if (!bCleaned) {
			// Go back
			int ny = robotCleaner._y - dy[robotCleaner._dir];
			int nx = robotCleaner._x - dx[robotCleaner._dir];

			// 뒤가 벽이라면 멈추고
			if (map[ny][nx] == 1)
				break;
			// 아니면 후진합니다.
			else {
				robotCleaner._y = ny;
				robotCleaner._x = nx;
				continue;
			}
		}
	}

	// 청소기가 멈춘 경우 답을 출력합니다.
	std::cout << nAnswer << "\n";
}