백준 14503번: 로봇 청소기

문제

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

코드

#include <vector>
#include <iostream>
#include<queue>
using namespace std;

int main() {
	int n, m, r, c, d;
	int count = 0;
	cin >> n >> m >> r >> c >> d;
	vector<vector<int>> map(n, vector<int>(m, 0));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> map[i][j];
		}
	}

	int dir[4][2] = { {-1,0},{0,1},{1,0},{0,-1} };
	queue<vector<int>> q;
	q.push({ r,c,d});

	while (!q.empty()) {
		int y = q.front()[0];
		int x = q.front()[1];
		int z = q.front()[2];
		bool t = false;
		q.pop();
		if (map[y][x] == 0) {
			map[y][x] = 2;
			count++;
		}
		for (int i = 0; i < 4; i++) {
			z--;
			if (z < 0) z += 4;

			int new_y = y + dir[z][0];
			int new_x = x + dir[z][1];
			if (map[new_y][new_x]==0) {
				t = true;
				q.push({ new_y, new_x, z });
				break;
			}		
		}
		if (t) continue;
		int new_y = y - dir[z][0];
		int new_x = x - dir[z][1];
		if ( map[new_y][new_x] != 1) {
			q.push({ new_y, new_x, z });
		}
		else break;		
	}
	cout << count;
}

풀이

bfs문제입니다. 2차원의 정사각형 맵에서 로봇청소기가 조건에 따라 움직일 때 청소한 칸의 개수를 구하면 됩니다.

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

기본적인 bfs알고리즘을 조금 변형해서 위의 조건대로 구현을 해줬습니다.