[C++] 백준 2210 : 숫자판 점프

[문제 풀이]
5*5 배열만 주어지기 때문에 완전탐색이 가능하다.

재귀호출을 통해 모든 경우의 수를 찾아준다.

수열에 대한 중복검사가 필요하다

[최초 제출]

#include <iostream>
#include <vector>

using namespace std;

vector <string> answer;
char Arr[5][5];

void dfs(int i, int j ,string num , int depth) {
	
	if (depth == 6) {
		bool duplicated = false;

		for (auto x : answer) {
			if (x == num) {
				duplicated = true;
			}
		}

		if (!duplicated) {
			answer.push_back(num);
		}

		return;
	}

	num += Arr[i][j];

	if (0 <= i + 1 && i + 1 < 5 && 0 <= j && j < 5) dfs(i+1, j, num, depth + 1);
	if (0 <= i  && i < 5 && 0 <= j + 1 && j + 1< 5) dfs(i , j+1, num, depth + 1);
	if (0 <= i - 1 && i - 1 < 5 && 0 <= j && j < 5) dfs(i-1, j, num, depth + 1);
	if (0 <= i && i < 5 && 0 <= j - 1 && j - 1 < 5) dfs(i,j-1, num, depth + 1);
}


int main() {

	for (int i = 0; i < 5; i++) {
		for (int j = 0; j < 5; j++) {
			cin >> Arr[i][j];
		}
	}

	for (int i = 0; i < 5; i++) {
		for (int j = 0; j < 5; j++) {
			dfs(i, j , "", 0);
		}
	}

	cout << answer.size();

}

[성능 개선 1]

경우의 수 구분이 굳이 문자열일 필요는 없다.

 

#include <iostream>
#include <vector>

using namespace std;

vector <int> answer;
int Arr[5][5];

void dfs(int i, int j ,int num , int depth) {
	
	if (depth == 6) {
		bool duplicated = false;

		for (auto x : answer) {
			if (x == num) {
				duplicated = true;
			}
		}

		if (!duplicated) {
			answer.push_back(num);
		}

		return;
	}

	num = 10*num + Arr[i][j];

	if (0 <= i + 1 && i + 1 < 5 && 0 <= j && j < 5) dfs(i+1, j, num, depth + 1);
	if (0 <= i  && i < 5 && 0 <= j + 1 && j + 1< 5) dfs(i , j+1, num, depth + 1);
	if (0 <= i - 1 && i - 1 < 5 && 0 <= j && j < 5) dfs(i-1, j, num, depth + 1);
	if (0 <= i && i < 5 && 0 <= j - 1 && j - 1 < 5) dfs(i,j-1, num, depth + 1);
}


int main() {

	for (int i = 0; i < 5; i++) {
		for (int j = 0; j < 5; j++) {
			cin >> Arr[i][j];
		}
	}

	for (int i = 0; i < 5; i++) {
		for (int j = 0; j < 5; j++) {
			dfs(i, j , 0, 0);
		}
	}

	cout << answer.size();

}

 

[성능 개선 2]
중복체크를 굳이 순회로 할 필요는 없다.
visited라는 DAT를 만들면 된다. 메모리는 조금 더 든다.

#include <iostream>
#include <vector>

using namespace std;

int answer = 0;
int Arr[5][5];
bool visited[1000000];

void dfs(int i, int j ,int num , int depth) {
	
	if (depth == 6) {
		if (!visited[num]) {
			answer++;
		}

		visited[num] = true;
		return;
	}

	num = 10*num + Arr[i][j];

	if (0 <= i + 1 && i + 1 < 5 && 0 <= j && j < 5) dfs(i+1, j, num, depth + 1);
	if (0 <= i  && i < 5 && 0 <= j + 1 && j + 1< 5) dfs(i , j+1, num, depth + 1);
	if (0 <= i - 1 && i - 1 < 5 && 0 <= j && j < 5) dfs(i-1, j, num, depth + 1);
	if (0 <= i && i < 5 && 0 <= j - 1 && j - 1 < 5) dfs(i,j-1, num, depth + 1);
}


int main() {

	for (int i = 0; i < 5; i++) {
		for (int j = 0; j < 5; j++) {
			cin >> Arr[i][j];
		}
	}

	for (int i = 0; i < 5; i++) {
		for (int j = 0; j < 5; j++) {
			dfs(i, j , 0, 0);
		}
	}
	
	cout << answer;

}

[가독성 개선]
반복되는 재귀 호출을 반복문으로 묶는게 바람직하다. 

#include <iostream>
#include <vector>

using namespace std;

int answer = 0;
int Arr[5][5];
bool visited[1000000];
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};

void dfs(int i, int j ,int num , int depth) {
	
	if (depth == 6) {
		if (!visited[num]) {
			answer++;
		}

		visited[num] = true;
		return;
	}

	num = 10*num + Arr[i][j];

	for (int d = 0; d < 4; d++) {
		int newI = i + dx[d];
		int newJ = j + dy[d];
		if (0 <= newI && newI < 5 && 0 <= newJ && newJ < 5) {
			dfs(newI, newJ, num, depth + 1);
		}
	}
}


int main() {

	for (int i = 0; i < 5; i++) {
		for (int j = 0; j < 5; j++) {
			cin >> Arr[i][j];
		}
	}

	for (int i = 0; i < 5; i++) {
		for (int j = 0; j < 5; j++) {
			dfs(i, j , 0, 0);
		}
	}
	
	cout << answer;

}