[BOJ 14503] 로봇 청소기 (C++)

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

14503번: 로봇 청소기

#include <vector>
#include <queue>
#include <map>
#include <utility>
#include <cstring>
#include <iostream>
using namespace std;

int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };
int graph[50][50];
bool visited[50][50];

class Info {
public:
	int r;
	int c;
	int d;
	Info(int r, int c, int d) : r(r), c(c), d(d)
	{}
};

map<int, int> pos = { {0,3},{1,0},{2,1}, {3,2} };
map<int, pair<int, int>> mov = { {0,make_pair(-1,0)}, {1,make_pair(0,1)},{2,make_pair(1,0)},{3,make_pair(0,-1)} };

bool backward(int r, int c, int d) {
	switch (d) {
	case 0:
		if (graph[r + 1][c] == 1)
			return false;
		else
			return true;
	case 1:
		if (graph[r][c-1] == 1)
			return false;
		else
			return true;
	case 2:
		if (graph[r-1][c] == 1)
			return false;
		else
			return true;
	case 3:
		if (graph[r][c+1] == 1)
			return false;
		else
			return true;
	}
}


int main() {
	int N, M, r, c, d;
	cin >> N >> M;
	int answer = 1;
	memset(visited, false, sizeof(visited));
	cin >> r >> c >> d;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> graph[i][j];
		}
	}
	queue<Info> q;
	visited[r][c] = true;
	q.push(Info(r, c, d));
	while (!q.empty()) {
		Info robot = q.front();
		q.pop();
		int curPos = robot.d;
		int curRow = robot.r;
		int curCol = robot.c;
		bool flag = false;
		for (int i = 0; i < 4; i++) {
			int left = pos[curPos];	//왼쪽 방향 
			curPos = left;		//그 방향으로 회전
			int nr = curRow+mov[left].first;
			int nc = curCol+mov[left].second;
			if (graph[nr][nc] == 0 && !visited[nr][nc]) {
				visited[nr][nc] = true;
				answer++;
				q.push(Info(nr, nc, curPos));
				flag = true;
				break;
			}
		}
		if (!flag && backward(robot.r, robot.c, robot.d)) {		//네 방향 모두 청소 되어있거나 벽인 경우 & 후진 가능할 경우
			if (robot.d == 0)		//후진
				robot.r += 1;
			else if (robot.d == 1)
				robot.c -= 1;
			else if (robot.d == 2)
				robot.r -= 1;
			else
				robot.c += 1;
			q.push(Info(robot.r, robot.c, robot.d));
		}
	}
	cout << answer << "\n";
	return 0;
}

심플한 구현으로도 풀리는 문제이지만.. 코드를 역시나 너무 길게 짠 듯 

여기서 포인트는 자기의 왼쪽 방향=(direction+3)%4 를 하면 나온다는 점. 

이 수식을 이용하면 자기 왼쪽 방향을 계속 탐색할 때 더 간편하게 할 수 있다.

 

bfs 방식으로,

왼쪽 방향에 청소할게 있으면 방문표시, answer+1 해주고 다시 큐로 돌아가서 탐색

없으면 계속해서 4번 탐색

flag 값 줘서 4번 탐색해도 없는 경우에는, 후진이 가능한지 체크하고 가능하면 또 큐에 넣어서 탐색하는 식이다

후진이 가능하지 않으면 큐에 아무것도 넣지 않는다

 

큐 사용을 하지 않아도 while(1) 문으로, 조건에 따라 이동하고, 이동한 좌표가 청소가능하면 ++1 하고, 더이상 움직일 수 없으면 답을 출력하는 방식을 사용해도 된다.