[백준 BOJ][C++]2210번 숫자판 점프 풀이: DFS

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

2210번: 숫자판 점프

 

 이 문제는 DFS로 해결할 수 있습니다. 

 

 다른 dfs 문제와는 다르게 한 번 방문한 위치를 중복하여 방문할 수 있기 때문에 방문 체크는 하지 않지만, 이미 생성된 6자리 숫자에 대해선 방문 표시를 해야하므로 bool visit[1000000]을 선언해야 합니다. 

 

 

[풀이 과정]

1. 숫자판을 입력받는다. 

2. 숫자판의 모든 좌표에 대해 dfs를 실행한다. 

3. 숫자판의 해당 좌표에 해당하는 숫자는 string으로 변환하여 탐색한다. 

4. 해당 좌표에서 이동 가능한 방향(상 하 좌 우)에 대하여 탐색을 진행한다. 

5. depth가 6이라면 string 타입의 숫자를 int 형으로 변환하여 이미 생성된 숫자인지 확인 후, 생성되지 않았다면 만들 수 있는 수들의 개수 ans를 증가시킨다. 

 

 

#include<iostream>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<string>

using namespace std;

bool visit[1000000] = { false, };
int num[5][5];
int ans;

void dfs(int x, int y, string number, int depth) {

	if (depth == 6) {

		int to_num = stoi(number);

		if (!visit[to_num]) {
			visit[to_num] = true;
			ans++;
		}

		return;
	}

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

	for (int i = 0; i < 4; i++) {
		int tx = x + dx[i];
		int ty = y + dy[i];

		if (tx < 0 || tx >= 5 || ty < 0 || ty >= 5)
			continue;

		string child_num = number;
		child_num.append(to_string(num[ty][tx]));
		dfs(tx, ty, child_num, depth + 1);
	}
}

int main(void) {

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

	for (int i = 0; i < 5; i++) {
		for (int j = 0; j < 5; j++) {
			string str = to_string(num[i][j]);
			dfs(j, i, str, 1);
		}
	}

	cout << ans;

	return 0;
}