[BOJ2210][C++] 숫자판 점프

2210번: 숫자판 점프

문제

임의의 시작점에서 상하좌우 네 방향으로 다섯 번 이동하며 만들 수 있는 6자리 수의 개수를 구한다.

 

해결

🎈Key Point🎈

dfs를 이용하여 문제를 해결한다.

 

모든 칸을 돌면서 그 칸을 시작점으로 하여 dfs를 돌려 만들 수 있는 모든 6자리 수를 구한다.

dfs를 실행시켜 시작점에서 상, 하, 좌, 우로 이동 후 각각에서 다시 dfs를 호출해 시작점에서부터 만들 수 있는 모든 6자리 수를 구한다.

구한 6자리 수는 set에 저장하여 중복되는 것을 제거하고 set.size()로 최종 6자리 수의 개수를 구한다.

 

[전체 코드]

#include <iostream>
#include <set>

using namespace std;

char board[5][5];
set<string> num_set;
string num = "000000";

void dfs(int x, int y, int cnt) {

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

	if (cnt == 6) {
		num_set.insert(num);
		return;
	}
	
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];

		if (nx >= 0 && nx < 5 && ny >= 0 && ny < 5) {
			num[cnt] = board[nx][ny];
			dfs(nx, ny, cnt + 1);
		}
	}
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

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

	cout << num_set.size();
}