백준 14503번 _로봇청소기

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

14503번: 로봇 청소기

풀이방법

그냥 주어진 이 조건들을 만족하는 dfs를 만들면된다.

 

1. 현재 위치를 청소한다.

2. 현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다.

 2. 1 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.

 2. 2 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.

 2. 3 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.

 2. 4 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.

 

 주의할점이 두가지 있는데, 방향이 북서남동이 아니라 북동남서인것과 후진할때 후진하는 dfs를 하나 더 만들어야 한다는점이다.  이 두가지만 주의한다면 어렵지 않다.

---

전체코드

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

using namespace std;
int map[52][52];
int N, M;
int robotX, robotY, d;
int dy[] = { -1, 0, 1, 0 };
int dx[] = { 0, -1, 0, 1 };

void Input()
{
	cin >> N >> M;
	cin >> robotY >> robotX >> d;
	if (d == 1)
		d = 3;
	else if (d == 3)
		d = 1;
	int value;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			cin >> value;
			if (value == 1)
				value = -1;
			map[i][j] = value;
		}
	}
}

bool inRange(int y, int x)
{
	if (y >= 0 && x >= 0 && y < N && x < M)
		return true;
	return false;
}

int cnt = 0;
bool isRun = true;
void dfs(int y, int x, int dir)
{
	if (isRun == false)
		return;

	//1. 현재위치를 청소한다.
	if(map[y][x] == 0)
		map[y][x] = ++cnt;

	//2. 현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다.
	for (int i = 0; i < 4; i++)
	{
		int ndir = (dir + i + 1)%4;
		int ny = y + dy[ndir];
		int nx = x + dx[ndir];

		if (inRange(ny, nx) == false)
			continue;

		if (map[ny][nx] == 0)
		{
			dfs(ny, nx, ndir);
			dir = ndir;
		}
		if (isRun == false)
			return;
	}
	
	//4 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.
	int by = y + dy[(dir + 2) % 4];
	int bx = x + dx[(dir + 2) % 4];
	if (inRange(by, bx) == false || map[by][bx]==-1)
	{
		isRun = false;
		return ;
	}
	//후진
	dfs(by, bx, dir);
}

void solve()
{
	dfs(robotY, robotX, d);
	cout << cnt << endl;

	/*테스트
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			cout << map[i][j] << ' ';
		}
		cout << endl;
	}*/
}

int main()
{
	Input();
	solve();
	return 0;
}

---

후기

방향이 북동남서인걸 보지못해 한 30분 삽질한거같다..ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

이런 구현문제는 진짜 사소한부분에서 실수를 줄이는게 중요한것 같다.