<C/C++> BOJ 14503 로봇청소기

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

14503번: 로봇 청소기

 

 

DFS를 사용해서 풀었다. 이전에 풀었던 문제와 좀 달랐던 부분은 보통 한 군데에서만 DFS를 실행하는 재귀함수 구조인데 이 경우에는 조건에 따라 두 군데에서 실행될 수 있다는 점이었다. 물론 한번만 실행되는 건 동일!

그리고 한 부분에서 실수했다. 문제에서 더 청소할 수 있는 공간 없으면 "방향을 유지한 채" 후진을 해야된다고 했었다. 하지만 "후진하는 방향으로 바꾸고" 풀어서 제대로 실행되지 않았었다.

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
#define MAXN 50
int N, M;
int R, C, D;
int map[MAXN+10][MAXN+10];
int visited[MAXN+10][MAXN+10];
static int dr[] = { -1, 0, 1, 0 };
static int dc[] = { 0, 1, 0, -1 };
int cnt;

void InputData(void) {
	cin >> N >> M;
	cin >> R >> C >> D;
	memset (map, 0, sizeof(map));
	for(int i = 0; i < N; i++) {
		for(int j = 0; j < M; j++) {
			cin >> map[i][j];
		}
	}
	visited[R][C] = 1;
	cnt ++;
}

void Solve(void) {
	int nr, nc, dir;
	int flag = 0;
	for(int i = 1; i <= 4; i++){
		dir = (D + 4 - i) % 4;
		nr = R + dr[dir];	// 왼쪽으로 돌린다
		nc = C + dc[dir];
		if(map[nr][nc] == 1 || visited[nr][nc]) continue; // 벽, 청소
		if(nr<0||nr>=N||nc<0||nc>=M) continue; // 범위 밖
		visited[nr][nc] = 1; 
		flag = 1; 
		R = nr, C = nc, D = dir;
		cnt ++;
		Solve();
		break;
	}
	if(flag == 0) { 
		dir = (D + 2) % 4; // 방향 유지한 채로 후진해야하는데 방향을 반대로 바꿈.
		R += dr[dir], C += dc[dir]; //후진
		if(R<0||R>=N||C<0||C>=M) return; // 범위 밖
		if (map[R][C] == 0) Solve(); // 후진할 수 있음
		else return; // 후진 못함
	}
	// 청소한 공간이라면 방향 돌리기
	// 네 방향 다 돌렸는데 다 청소했고 벽이면
	// 후진하기
	// 후진도 못하면 끝
	// 청소안했으면 전진해서 청소하기
	
}
int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	InputData();
	Solve();
	cout<<cnt<<endl;
	return 0;
}