백준 14503 로봇 청소기

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

14503번: 로봇 청소기

 

- N x M 크기의 장소가 주어진다. 테스트 케이스 마음이라 시간복잡도는 구할 수 없다고 생각..

 

- 벽인지 바닥인지 여부를 나타내는 place array, 그리고 청소가 된 지 여부를 체크하는 cleaned array를 두었다.

 

- 방향은 x, y 각각 배열을 두어서, 북 : 0, 동 : 1, 남 : 2, 서 : 3 각 값을 index로 사용하도록 하였다. 즉, 현재 x,y에 해당 인덱스의 값들을 더해주면 해당 위치로 이동 하였을 때의 좌표가 나온다.

 

- 보통 out of range도 체크를 해야 하지만, 이 문제는 NxM 테두리가 벽으로 막혀있었기에 out of range 체크는 하지 않아도 되었다.

 

- 실제로 청소를 하는 경우는 1. 시작 시, 2. case a에 해당할 때 뿐이어서 해당 case일 때만 answer를 증가시켜주었다. 다른 방법으로는 while문을 벗어난 후 cleaned를 for loop을 돌면서 true인 경우 answer++ 해 주어도 될 것이다.

 

- c와 d 케이스를 while문 내부에서 먼저 체크한 이유는, 만약 b 케이스를 먼저 체크를 한다면 네 방향을 모두 체크해야 하는 상황에서 왼쪽에 청소할 공간이 없기만 해도 바로 b 케이스에 대한 처리로 넘어가므로 c와 d 케이스로 갈 수 없게 되었기 때문이다.

 

- 문제에 쓰여있는 대로 잘 구현만 하면 어렵지 않은 문제였다.

 

#include <iostream>
using namespace std;
int dx[] = { -1, 0, 1, 0 };
int dy[] = { 0, 1, 0, -1 };
int place[50][50];
bool cleaned[50][50];
int main() {
	int n, m;
	cin >> n >> m;
	int x, y, dir;
	cin >> x >> y >> dir;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> place[i][j];
		}
	}
	int answer = 1;
	cleaned[x][y] = true;
	while (1) {
		int cnt = 0;
		for (int i = 0; i < 4; i++) {
			int temp_x = x + dx[i];
			int temp_y = y + dy[i];
			if (place[temp_x][temp_y] || cleaned[temp_x][temp_y]) cnt++;
		}
		if (cnt == 4) { // c 또는 d 케이스
			int backward_dir = (dir + 2) % 4;
			x = x + dx[backward_dir];
			y = y + dy[backward_dir];
			if (place[x][y]) break; // d, 종료
			else continue;
		}
		int left_dir = (dir + 3) % 4; 
		int nx = x + dx[left_dir];
		int ny = y + dy[left_dir];
		// a 케이스 
		if (!place[nx][ny] && !cleaned[nx][ny]) {
			dir = left_dir;
			x = nx; y = ny;
			cleaned[nx][ny] = true;
			answer++;
		}
        // b 케이스
		else {
			dir = left_dir;
		}
	}
	cout << answer;
}