[백준 14503] 로봇 청소기

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

14503번: 로봇 청소기

 

 

문제에서 주어진 방향 순서대로 x, y 좌표 값을 x_dir[], y_dir[]에 각각 저장해두고 사용하였으며 로봇 청소기의 동작 순서대로 코드를 구현하였다.

1. 현재 위치와 방향을 기준으로 왼쪽 방향으로 한 바퀴 탐색하면서 해당 좌표를 청소하지 않았다면 방향, 좌표를 바꾸고 새로운 방향과 좌표로 재귀호출해 준다.
2. 네 방향 이미 방문했거나 벽이라면 로봇 청소기의 방향은 유지하고 좌표만 뒤로 한 칸 후진한다.
3. 후진조차 할 수 없는 상황이라면 cnt를 출력하고 동작을 멈춘다.

전형적인 DFS 문제라 구현자체는 어렵지 않았으나 y좌표의 시작점이 어디인지 착각해서 잘못된 부분을 찾는데 시간이 좀 걸렸다. 

 

 

#include <iostream>
using namespace std;

int n, m;
int map[51][51];
bool visited[51][51];
int r, c, d;
int cnt = 1;
int x_dir[] = { 0,1,0,-1 };
int y_dir[] = { -1,0,1,0 };

void cleaning(int y, int x, int dir) {
	bool canMove = false;
	visited[y][x] = true;
	
	for (int i = 0; i < 4; i++) {
		int nextDir = (dir + 3 - i) % 4;
		int leftY = y + y_dir[nextDir];
		int leftX = x + x_dir[nextDir];
		if (leftY >= 0 && leftY < n && leftX >= 0 && leftX < m) {
			if (!map[leftY][leftX] && !visited[leftY][leftX]) {
				canMove = true;
				cnt++;
				cleaning(leftY, leftX, nextDir);
			}
		}
	}
	if (!canMove) {
		int backDir = (dir + 2) % 4;
		int backY = y + y_dir[backDir];
		int backX = x + x_dir[backDir];
		if (backY >= 0 && backY < n && backX >= 0 && backX < m) {
			if (!map[backY][backX])
				cleaning(backY, backX, dir);
			else {
				cout << cnt;
				exit(0);
			}
		}
	}
}
int main() {
	cin >> n >> m;
	cin >> r >> c >> d;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++)
			cin >> map[i][j];
	}
	cleaning(r, c, d);
	cout << cnt;

}