[C/C++ 백준 2210번] 숫자판 점프 (Silver 2)

www.acmicpc.net/problem/2210

2210번: 숫자판 점프

5*5의 사이즈라, 모든 경우를 다 탐색해도 시간 초과가 나지 않는다. 말그대로 모든 점에서 시작해서 모든 경우를 찾으면 되는데, 재귀함수를 이용해서 6번 이동하게 구현해주면 된다. 

 

이후 겹치는지에 대한 여부를 알기 위해 6자리 숫자를 실제로 만들어주고, vector안에 집어 넣은 뒤 중복된 원소들을 제거한 후 size를 출력해주자.

 

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
vector <int> answer;
int returnpow(int n){
	int a = 1;
	for(int i=0; i<n; i++){
		a *= 10;
	}
	return a;
}
int xmove[4]={-1,1,0,0};
int ymove[4]={0,0,1,-1};
int array[5][5];
void dfs(int x, int y, int cnt, int dp){
	if(cnt==6){
		answer.push_back(dp);
		return;
	}
	else{
		dp += array[x][y]*returnpow(cnt);
	for(int i=0; i<4; i++){
		if(x+xmove[i]>=0 &&x+xmove[i]<5){
			if(y+ymove[i]>=0 &&y+ymove[i]<5){
				dfs(x+xmove[i], y+ymove[i], cnt+1, dp);
			}
		}
	}
	}
	
}
int main(void){
	for(int i=0; i<5; i++){
		for(int j=0; j<5; j++){
			scanf(" %d", &array[i][j]);
		}
	}
	for(int i=0; i<5; i++){
		for(int j=0; j<5; j++){
			dfs(i, j, 0, 0);
		}
	}
	sort(answer.begin(), answer.end());
	answer.erase(unique(answer.begin(), answer.end()), answer.end());
	printf("%d", answer.size());
}