문제

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

풀이

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility> 
#include <cstring> 
#include <queue> 
#define MAX 51 
using namespace std; 

int n, m; 
int graph[MAX][MAX]; // 빈칸은 0, 벽은 1 
bool cleaned[MAX][MAX]; // 청소되면 true, 아니면 false 
int cnt = 0; // 청소한 칸의 개수 

// 북 0 동 1 남 2 서 3  
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};

void dfs(int x, int y, int d){ 
	// 1. 현재 칸이 청소되지 않은 경우 청소한다.
	if(!cleaned[x][y]){ 
		cleaned[x][y] = true; 
		cnt++; 
	}
	
	// 3. 바라보는 방향 d를 기준으로 반시계 방향으로 탐색 
	for(int i = 0; i < 4; i++){ 
		int nd = (d + 3 - i) % 4; // 반시계 방향 
		int nx = x + dx[nd]; 
		int ny = y + dy[nd]; 

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

		// 청소되지 않은 빈칸을 발견한 경우 
		if(graph[nx][ny] == 0 && !cleaned[nx][ny]){ 
			// "방향을 회전하여" 한칸 전진한다. 
			dfs(nx, ny, nd); 
		} 
	}

	// 2. 주변 4칸 중에 청소되지 않은 빈칸이 없는 경우, 후진 가능 여부 탐색 
	int back = (d + 2) % 4; // 후진 방향 
	int bx = x + dx[back]; 
	int by = y + dy[back]; 

	// 범위를 벗어나거나 벽을 마주치면 작동을 멈춘다. 
	if(bx < 0 || bx >= n || by < 0 || by >= m || graph[bx][by] == 1) {
		cout << cnt; 
		exit(0); 
	}
	
	// "바라보는 방향 유지한 채로" 한칸 후진한다. 
	dfs(bx, by, d);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m; 

	int r, c, d; 
	cin >> r >> c >> d;

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

	dfs(r, c, d);
	
    return 0;
}

주변 4칸을 탐색하여 청소되지 않은 빈칸을 발견한 경우에는 회전 방향을 nd로 바꿔줘야 한다. 하지만, 후진할 때는 바라보는 방향 d를 그대로 유지한 채로 후진해야 한다. 방향 전환에 유의해서 풀어야 하는 문제였다..!!

	// 3. 바라보는 방향 d를 기준으로 반시계 방향으로 탐색 
	for(int i = 0; i < 4; i++){ 
		int nd = (d + 3 - i) % 4; // 반시계 방향 
		int nx = x + dx[nd]; 
		int ny = y + dy[nd]; 

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

		// 청소되지 않은 빈칸을 발견한 경우 
		if(graph[nx][ny] == 0 && !cleaned[nx][ny]){ 
			// "방향을 회전하여" 한칸 전진한다. 
			dfs(nx, ny, nd); // d가 아니라 nd로 바꿔줘야 한다!! 
		} 
	}

	// 2. 주변 4칸 중에 청소되지 않은 빈칸이 없는 경우, 후진 가능 여부 탐색 
	int back = (d + 2) % 4; // 후진 방향 
	int bx = x + dx[back]; 
	int by = y + dy[back]; 

	// 범위를 벗어나거나 벽을 마주치면 작동을 멈춘다. 
	if(bx < 0 || bx >= n || by < 0 || by >= m || graph[bx][by] == 1) {
		cout << cnt; 
		exit(0); 
	}
	
	// "바라보는 방향 유지한 채로" 한칸 후진한다. 
	dfs(bx, by, d); // d를 유지시켜줘야 한다!!