[BOJ] 14503번_로봇청소기_DFS (C++)

[문제]

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

로봇 청소기 위치와 방의 상태가 주어졌을 때, 로봇 청소기가 청소를 하는 영역의 개수를 구하는 프로그램을 만드는 문제이다.
로봇 청소기가 이동하는 로직은 다음과 같다.

1. 현재 칸이 아직 청소되지 않은 경우, 현재 칸을 청소한다.
2. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 없는 경우,
   2-1. 바라보는 방향을 유지한 채로 한 칸 후진할 수 있다면 한 칸 후진하고 1번으로 돌아간다.
   2-2. 바라보는 방향의 뒤쪽 칸이 벽이라 후진할 수 없다면 작동을 멈춘다.
3. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 있는 경우,
   3-1. 반시계 방향으로 90° 회전한다.
   3-2. 바라보는 방향을 기준으로 앞쪽 칸이 청소되지 않은 빈 칸인 경우 한 칸 전진한다.
   3-3. 1번으로 돌아간다.

• 나는 이 문제를 혼자 해결하지 못해 인터넷 검색을 통해 도움을 받았다.

[사용 알고리즘]

DFS(깊이 우선 탐색)

[풀이 핵심]

• 이 문제가 어려운 이유는 로봇 청소기가 후진하는 기능이 있기 때문이다. DFS를 돌때 조건에 의해 후진을 하게 되면 좌표가 바뀌게 되는데, 이 좌표가 이전 DFS를 실행한 좌표와 다를 수 있다. 그래서 이전 DFS로 돌아가야 할 때, 후진한 좌표에서 DFS를 시작하도록 만들어야한다.
• main 함수에서는 일반적으로 "return 0" 를 통해 프로그램을 종료할 수 있는데, 일반 함수에선 return 0 를 사용할 수 없다. 하지만 "exit()" 함수를 통해 일반 함수에서도 프로그램을 종료할 수 있다.
  ->exit(0) : 정상적인 경우의 프로그램 종료
  ->exit(1) : 비정상적인 경우의 프로그램 종료

[코드]

//boj14503번_로봇청소기_그래프

#include<iostream>

using namespace std;

int graph[52][52];
bool visited[52][52];

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

int result = 0;

int N, M;

void DFS(int x, int y, int dir) {
	if (visited[x][y] == false) {
		result++;
	}

	visited[x][y] = true;

	for (int i = 0; i < 4; i++) {
		int next_dir = (dir + 3 - i) % 4;

		int next_x = x + dx[next_dir];
		int next_y = y + dy[next_dir];

		if (next_x >= 0 && next_x < N && next_y >= 0 && next_y < M && graph[next_x][next_y] == 0 && !visited[next_x][next_y]) {
			DFS(next_x, next_y, next_dir);
		}
	}

	int back_dir = (dir + 2) % 4;

	int next_x = x + dx[back_dir];
	int next_y = y + dy[back_dir];

	if (graph[next_x][next_y] == 1) {
		cout << result;
		exit(0);
	}

	DFS(next_x, next_y, dir);
}

int main() {
	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);

	cout << result;

	return 0;
}