[BAEKJOON] 14503번 로봇 청소기

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

14503번: 로봇 청소기

문제조건 

1. 현재 칸이 아직 청소되지 않은 경우, 현재 칸을 청소한다.
2. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 없는 경우,
   1. 바라보는 방향을 유지한 채로 한 칸 후진할 수 있다면 한 칸 후진하고 1번으로 돌아간다.
   2. 바라보는 방향의 뒤쪽 칸이 벽이라 후진할 수 없다면 작동을 멈춘다.
3. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 있는 경우,
   1. 반시계 방향으로 90º 회전한다.
   2. 바라보는 방향을 기준으로 앞쪽 칸이 청소되지 않은 빈 칸인 경우 한 칸 전진한다.
   3. 1번으로 돌아간다.

접근방법

 

문제 조건이 엄청 까다로운 것을 보고 바로 어려운 알고리즘을 요구하지는 않겠다는 문제임을 직감했다.

문제는 정말 단순했다. 그냥 BFS로 청소기를 기준으로 상하좌우를 탐색해주고, 빈 칸을 체크 해줬다.

 

주의점

 

1. 문제 요구 조건에서 방향을 잘봐야한다.
   0인 경우 북쪽, 
   1인 경우 동쪽, 
   2인 경우 남쪽, 
   3인 경우 서쪽
2. 방향 설정
   1. 방향을 바라보는 쪽일 경우에는 방향 자체를 바꾸고
   2. 방향을 바라보고 뒤로 갈때는 방향 자체를 바꾸면 안된다.
3. 청소한 방은 벽이 아닌, 다른 표시로 청소했다고 해줘야한다.
4. 문제 조건3-2를 지키지 못할경우 큐에 계속해서 같은 좌표를 넣어줘야한다.

소스코드

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

int n, m, r, c, d, map[51][51];

int dy[] = { -1, 0, 1, 0 };
int dx[] = { 0, 1, 0, -1 };
int res;

void bfs() {
	queue<pair<int, int> > q;
	q.push({ r,c });
	while (!q.empty()) {
		bool judge = false;
		int y = q.front().first;
		int x = q.front().second;
		if (!map[y][x]) {
			res++;
			map[y][x] = 2;
		}
		q.pop();
		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (ny >= n || ny < 0 || nx >= m || nx < 0) continue;
			if (!map[ny][nx]) {
				judge = true;
			}
		}
		if (judge == false) {
			//반대 방향
			int dir = (d + 2) % 4;
			int ny = y + dy[dir];
			int nx = x + dx[dir];
			if (map[ny][nx] != 1) {
				q.push({ ny,nx });
				continue;
			}
			else break;
		}
		else {
			//반시계방향
			d = (d + 3) % 4;
			int ny = y + dy[d];
			int nx = x + dx[d];
			if (!map[ny][nx]) q.push({ ny,nx });
			else q.push({ y,x });
			continue;
		}
	}
}



// 0 : 청소되지 않은 빈칸	1 : 벽
int main(){
	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];
		}
	}
	bfs();
	cout << res;
}

 

문제 조건만 꼼꼼히 본다면 누구나 풀 수 있다고 생각하는 문제다,,!