백준 14503번 로봇청소기 (DFS)

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

14503번: 로봇 청소기

 

쉬울 줄 알았는데 생각보다 구현이 어려웠던 문제이다.

dfs를 이용해서 구현하였으며 방향을 설정해주는 dir 변수도 파라미터로 사용했다.

 

왼쪽 방향순으로 회전해줘야 하며 현재 방향과 나머지 연산을 이용해서 다음 방향을 설정했다.

4번 반복을 수행하며 다음 위치의 값이 0이면 재귀로 dfs를 호출한다.

 

주의할 점은 4방향을 모두 돌고나서 다음 위치로 진행이 불가능한 경우 1칸 후진을 해야한다.

이때, 후진할 위치의 값이 1이면 exit(0)을 이용하여 재귀를 종료하고 아닌 경우 다시 재귀를 호출하는 방식으로 구현한다.

 

<소스코드>

#include<iostream>
#include<queue>

using namespace std;

int n, m;
int map[51][51];

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

int ans;

void dfs(int cx, int cy, int cd) {
	if (map[cx][cy] == 0) {
		map[cx][cy] = 2;
		ans++;
	}

	for (int i = 0; i < 4; i++) {
		int nd = (cd + 3 - i) % 4;
		int nx = cx + dx[nd];
		int ny = cy + dy[nd];

		if (nx < 0 || ny < 0 || nx >= n || ny >= m) {
			continue;
		}

		if (map[nx][ny] == 0) {
			dfs(nx, ny, nd);
		}
	}
	
	int nd = (cd + 2) % 4;
	int nx = cx + dx[nd];
	int ny = cy + dy[nd];

	if (map[nx][ny] == 1) {
		cout << ans << '\n';
		exit(0);
	}
	dfs(nx, ny, cd);
}


int main(void) {
	cin >> n >> m;
	
	int r, c, dir;
	cin >> r >> c >> dir;

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

	dfs(r, c, dir);

	return 0;
}