[프로그래머스 Level 2] 리코쳇 로봇(C++)

코딩테스트 연습 - 리코쳇 로봇 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

dfs방식으로 상하좌우로 각각 가주는 방식으로 해주었다. 시간초과 방지를 위해 checked 2차원 배열을 이용해 각 장소에서 도달했을 때의 횟수를 저장해주었고, checked[i][j]에서의 값보다 현재 도달한 횟수가 크거나 같을 때 혹은, 현재 G를 찾았을 떄의 횟수보다 cnt 값이 클 때 dfs 탐색을 멈추는 방식을 했다.

 

#include <string>
#include <vector>

using namespace std;

int N, M;
vector<string> maps;
int checked[100][100];
int minNum = 987654321;

void dfs(int i, int j, int cnt) {
	if (checked[i][j]<=cnt || cnt >= minNum)
		return;
	if (maps[i][j] == 'G') {
		minNum = min(minNum, cnt);
	}
	checked[i][j] = cnt;
	int x = j;
	while (x != -1 && maps[i][x] != 'D') {
		x--;
	}
	x++;
	dfs(i, x, cnt + 1);
	x = j;
	while (x != maps[0].size() && maps[i][x] != 'D') {
		x++;
	}
	x--;
	dfs(i, x, cnt + 1);
	int y = i;
	while (y != -1 && maps[y][j] != 'D') {
		y--;
	}
	y++;
	dfs(y, j, cnt + 1);
	y = i;
	while (y != maps.size() && maps[y][j] != 'D') {
		y++;
	}
	y--;
	dfs(y, j, cnt + 1);
}

int solution(vector<string> board) {
	int answer = 0;
	maps = board;
	N = board.size();
	M = board[0].size();
	int rY = 0, rX = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (board[i][j] == 'R') {
				rY = i;
				rX = j;
				break;
			}
		}
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			checked[i][j] = 987654321;
		}
	}
	dfs(rY, rX, 0);
	if (minNum == 987654321) {
		answer = -1;
	}
	else {
		answer = minNum;
	}
	return answer;
}