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

백준 14503번.

사용한 알고리즘

- bfs

 

방향을 설정하기가 조금 까다로웠던 문제.... 

청소한 곳을 체크하기 위한 visited 배열을 두었다.

시작 지점을 큐에 넣고 bfs 시작. 

1. 현재 지점의 visited 배열을 true로

2. 현재 방향을 기준으로 왼쪽 부터 차례대로 탐색한다. 나는 아예 배열을 따로 만들어서 현재 청소기가 바라보는 방향인 d에 따라서 탐색할 순서를 설정해줬다. 문제에서 주어진 d 의 순서도 왼쪽방향이면 이렇게 안해도 됐을 텐데.. d의 값은 오른쪽 방향으로 증가하고, 실제 인접한 부분 탐색은 반대 방향으로 해주어야 해서 그냥 배열 하나 더만들어서 편하게 했다.

    a~ d 까지는 문제에 주어진대로 그대로 알고리즘을 짜면 된다. 처음에는 그냥 청소한부분 map 값을 1로 만들어버리려했는데, 벽이아니     면 후진하는 조건이 있어서 visited 배열을 만들어 줬다.  

 

 

완성된 코드

#include <stdio.h>
#include <vector>
#include <queue>

using namespace std;

int n, m;
int r, c, d;
vector<vector<int>> map;
vector<vector<bool>> visited;

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

int a[4][4] = {
	{0, 3, 2, 1},
	{1, 0, 3, 2},
	{2, 1, 0, 3},
	{3, 2, 1, 0}
};

int ans = 0;
// d = 0 위 1 오 2 아래 3 왼

void bfs(int x, int y) {
	queue<pair<int, int>> q;
	q.push(make_pair(x, y));
	visited[x][y] = true; // 청소한다.
	ans++;
	while(!q.empty()) {
		int cx = q.front().first;
		int cy = q.front().second;
		q.pop();
		bool flag = false;
		for(int i = 0; i < 4; ++i) {
			int nx = cx + dx[a[d][i]];
			int ny = cy + dy[a[d][i]];
			if (map[nx][ny] == 0 && !visited[nx][ny]) {
				q.push(make_pair(nx, ny));
				ans++;
				visited[nx][ny] = true;
				if (a[d][i] == 0)
					d = 3;
				else if (a[d][i] == 1)
					d = 0;
				else if (a[d][i] == 2)
					d = 1;
				else
					d = 2;
				flag = true;
				break;
			} else {
				continue;
			}
		}
		if (!flag) {
			if (d == 0 && cx + 1 < n && map[cx + 1][cy] == 0) {
				// 아래로
				q.push(make_pair(cx + 1, cy));
			} else if (d == 1 && cy - 1 >= 0 && map[cx][cy - 1] == 0) {
				// 왼쪽
				q.push(make_pair(cx, cy - 1));
			} else if (d == 2 && cx - 1 >= 0 && map[cx - 1][cy] == 0) {
				// 위로
				q.push(make_pair(cx - 1, cy));
			} else if (d == 3 && cy + 1 < m && map[cx][cy + 1] == 0) {
				// 오른쪽
				q.push(make_pair(cx, cy + 1));
			} else {
				while(!q.empty())
					q.pop();
			}
		}
	}
}

int main() {
	scanf("%d %d %d %d %d", &n, &m, &r, &c, &d);
	map.assign(n + 1, vector<int>(m + 1));
	visited.assign(n + 1, vector<bool>(m + 1, false));
	for(int i = 0; i < n; ++i) {
		for(int j = 0; j < m; ++j) {
			scanf("%d", &map[i][j]);
		}
	}
	bfs(r, c);
	printf("%d\n", ans);
}