백준 BOJ 2210 - 숫자판 점프

USACO(3)

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

2210번: 숫자판 점프

 

판의 크기가 작고, 탐색 깊이가 깊지 않아서

브루트포싱으로도 충분히 문제를 해결할 수 있다.

 

4방향^6회 * 25가지 좌표

대략 10만번쯤 탐색할거같다.

 

6번 탐색하기 때문에 6번을 탐색해 만들어진 가장 큰 숫자는

999999 이므로, int범위도 벗어나지 않고, 문자열으로 붙여서 관리하는게 아니라

그냥 int로 관리해도 문제가 없다.

 

나는 dfs로 구현해주었다.

 

소스코드 펼쳐보기

#include <bits/stdc++.h>
using namespace std;

int arr[6][6] = {0};
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};
set<int> st;

void dfs(int x, int y, int num, int len){
	if(len == 6){
		st.insert(num);
		return;
	}
	
	for(int i=0; i<4; i++){
		int nx = x + dx[i];
		int ny = y + dy[i];
		if(1<=nx && nx<=5 && 1<=ny && ny<=5){
			dfs(nx,ny,num*10+arr[nx][ny],len+1);
		}
	}
}

int main(){
	for(int i=1; i<=5; i++){
		for(int j=1; j<=5; j++){
			cin >> arr[i][j];
		}
	}
	
	for(int i=1; i<=5; i++){
		for(int j=1; j<=5; j++){
			dfs(i,j,arr[i][j],1);
		}
	}
	cout << st.size();
}