[백준 14503] 로봇 청소기

문제 출처: https://www.acmicpc.net/problem/14503

풀이

최초의 로봇청소기의 좌표로부터 4방향을 검색하면서 방향을 바꾸는 연산이 너무 까다로웠습니다..

로봇 청소기의 좌표 및, 방향을 담을 수 있는 큐를 선언하여 bfs를 이용했습니다. 

현재 자리에서 왼쪽부터 탐색하여 벽이있거나, 이미 청소했을 경우, 방향을 그 쪽으로 돌리는게 핵심이었습니다. 

문제에서 주어진대로 0번 인덱스:북, 1번: 동, 2번 : 남, 3번 서 쪽으로 각각 지정해서 dx[4],dy[4] 좌표를 선언했습니다. 

bfs 수행중에 중요한것은, 네 방향을 방향 순서에 따라 탐색 중, 청소할 수 있는 좌표를 만나면 좌표를 남기고 탈출해야합니다.(4번연산하지않게)

왼쪽부터 탐색하여 향하는 방향을 갱신해주는 연산 코드는 아래와 같습니다. (이게 너무 어려웠습니다.) 매번 향하는 순서가 규칙적이므로, 아래 코드가 성립합니다.

int next_go = (go + (3 - i)) % 4;

그리고 두번 쨰로 까다로운 연산은 후진 할 떄, 방향은 유지하며 후진하는 것입니다. 그런데 사실 까다로운건 없습니다. 아래와 같이 작성하면 이게 곧 그 뜻이됩니다.

int by = y - dy[go];

int bx = x - dx[go];

이렇게 식을 세울줄 알면 끝이라서,, 나머지설명은 주석으로 확인해주세요.

코드

#include<iostream>
#include<queue>
using namespace std;
int map[50][50];
int dy[4] = { -1,0,1,0 };
int dx[4] = { 0,1,0,-1 };
int n, m, r, c, d, room;
queue<pair<pair<int, int>,int>> q;
void bfs();
int main()
{
	cin >> n >> m >> r >> c >> d;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			cin >> map[i][j];

	bfs();
	cout << room;
}
void bfs()
{
	q.push({ {r,c},d });
	while (!q.empty())
	{
		int y = q.front().first.first;
		int x = q.front().first.second;
		int go = q.front().second;
		if (map[y][x] == 0)
		{
			room++;
			map[y][x] = 10;
		}
		q.pop();
		bool check = false;
		for (int i = 0; i < 4; i++)
		{
			//좌표의변화. 이게 너무어려웠음
			int next_go = (go + (3 - i)) % 4;

			int ny = y + dy[next_go];
			int nx = x + dx[next_go];
			//(1,0)인상태)
			if (nx >= 0 && ny >= 0 && nx < m && ny < n)
			{
				if (map[ny][nx] == 0)
				{
					q.push({ {ny,nx},next_go });
					check = true;
					break;
				}
				
			}
		}

		//네 방향 모두 청소되어있을떄 || 네방향모두 벽일 때
		if (!check)
		{
			//방향을 유지하며 한칸 후진. 
			int by = y - dy[go];
			int bx = x - dx[go];
			//후진할 수 있으면 후진해서 다시 시작
			if ((0 <= by && by < n && 0 <= bx && bx < m) && map[by][bx] != 1)
				q.push({ {by, bx}, go });
			//후진할 수 없으면 종료
			else
				break;
		}
		//빈칸을 찾아서 청소하러 이동한경우 skip
		else
			continue;
	}
}

결과