[알고리즘] 백준 14503 로봇 청소기

백준 14503

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

14503번: 로봇 청소기

 

풀이 전 나의 생각

오랜만에 푸는 양방향 탐색이어서 굉장히 헷갈렸다..

정말 조건 그대로 코드를 짜면 풀리는 문제이긴 한데 엄청 헤멨던 부분이 있어서

인터넷을 찾아보고 겨우겨우 풀었다.

 

우선 이 문제에서 중요한 부분은

1. 양방향 탐색은 현재 로봇 청소기 방향을 기준으로 하니 dx, dy 값을 0, 1, 2, 3의 각 방향에 맞게 설정해줘야 한다.

2. 로봇 청소기가 주변 4곳의 탐색이 끝난 후 다시 원래 방향으로 돌아와야 하니 미리 방향을 왼쪽으로 꺾어서 탐색한다 -> (d + 3) % 4

3. 벽을만나면 무조건 종료.

 

이 3가지를 주의해서 풀면 좋다.

 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;

int room[52][52];
bool cleaned[52][52];

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

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n, m, r, c, d, cnt = 0;
	cin >> n >> m >> r >> c >> d;

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			cin >> room[i][j];
		}
	}

	while (true)
	{
		if (cleaned[r][c] == false)
		{
			cleaned[r][c] = true;
			cnt++;
		}

		bool isClean = false;

		for (int i = 0; i < 4; i++)
		{
			d = (d + 3) % 4;
			int nx = r + dx[d];
			int ny = c + dy[d];

			if (room[nx][ny] == 0 && cleaned[nx][ny] == false)
			{
				r += dx[d];
				c += dy[d];
				isClean = true;
				break;
			}
		}

		if (!isClean)
		{
			int back = (d + 2) % 4;
			if (room[r + dx[back]][c + dy[back]] == 1) break;

			r += dx[back];
			c += dy[back];
		}
	}

	cout << cnt;
}