[백준 14503번] 로봇 청소기 C++

[백준 14503번 로봇 청소기]
https://www.acmicpc.net/problem/14503

단순한 구현 문제였지만 문제 이해를 제대로 하지 못해 상당히 오래 걸린 문제였다. 쉽게 쉽게 생각해서 풀었으면 더 빨리 풀었을 것 같다.

풀이 방법

로봇 청소기는 다음과 같이 작동한다.

1.현재 위치를 청소한다.

2.현재 위치에서 현재 방향을 기준으로 왼쪽 방향부터 차례대로 인접한 칸을 탐색한다.

-왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.

-왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.

-네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.

-네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.

로봇 청소기는 이미 청소되어있는 칸을 또 청소하지 않으며, 벽을 통과할 수 없다.

"왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면"이라는 부분을 내가 바라보는 방향에서 왼쪽으로 방 끝까지 전부 다 확인해서 한 칸이라도 청소하지 않은 공간이 존재한다면으로 생각해버렸다(생각해보면 말도 안 되는 생각이다).

예제 케이스를 계속 통과할 수 없자 천천히 다시 읽어보고 잘못 생각했다는 것을 깨달았다.
풀이 방법은 주어진 조건 그대로를 따라하면 된다.

2중 while문을 사용했기 때문에 바깥 while문은 done이라는 bool 타입을 줘서 작동이 끝나면 바깥 while문을 끝낼 수 있도록 구현했다.
네 방향 모두 청소할 수 있는 공간이 없다는 부분은 로봇 청소기가 네 방향을 모두 돌며 탐색한 이후와 같기 때문에 turns라는 정수 타입 변수의 값이 4가 될 때로 구현했다.

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <utility>  // pair
#include <tuple>
#include <stack>
#define ll long long
#define INF 1e9
using namespace std;

int n,m;
int r,c;
int d;
int cnt = 0;
int map[51][51];
int lr[] = {0,-1,0,1};
int lc[] = {-1,0,1,0};

int br[] = {1,0,-1,0};
int bc[] = {0,-1,0,1};
bool visited[51][51];
bool done = false;

void turnLeft(int &d) {
	d = (d+3) % 4;
	return;
}

void sol() {
	while(!done) {
		if(!visited[r][c]) {
			visited[r][c] = true;
			cnt++;
		}

		int turns = 0;
		while(true) {
			if(!visited[r][c]) {
				visited[r][c] = true;
			}

			if(turns == 4) {
				turns = 0;
				if(map[r + br[d]][c + bc[d]] == 1) {
					done = true;
					break;
				} else {
					r += br[d];
					c += bc[d];
					continue;
				}
			}

			int nr = r + lr[d];
			int nc = c + lc[d];

			if(!visited[nr][nc] && map[nr][nc] == 0) {
				turnLeft(d);
				r = nr; c = nc;
				break;
			} else {
				turnLeft(d);
				turns++;
				continue;
			}

			
		}
	}
}

int main(void) {
	ios_base :: sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);


	cin >> n >> m;
	cin >> r >> c >> d;


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

	sol();

	cout << cnt << '\n';
	
	return 0;
}