[BOJ] 2210번_숫자판 점프_DFS (C++)

[문제]

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

0~9의 숫자가 적혀 있는 5X5 크기의 그래프에서 임의의 위치에서 시작해 인접해 있는 4방향으로 다섯 번 이동하면서 6자리 숫자를 만들었을 때, 만들 수 있는 숫자의 개수를 구하면 되는 문제이다. (중복X)

[사용 알고리즘]

DFS(깊이 우선 탐색), 브루트포스 알고리즘

[풀이 핵심]

• 5X5 그래프에 6자리 숫자이므로 브루트포스 알고리즘을 사용해도 시간초과가 나지 않는다.
• 중복된 숫자는 저장하지 않기 위해 set을 사용했다.
• DFS를 사용해서 cnt가 6이 됐을 때, set에 값을 저장했다.
• 1자리 수 6개로 6자리 수를 만드는 방식이므로 string타입의 변수를 사용했다.

[코드]

//boj2210번_숫자판 점프_그래프

#include<iostream>
#include<set>

using namespace std;

char graph[5][5];

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

set<string> result;

void DFS(int x, int y, string num, int cnt) {
	if (cnt == 6) {
		result.insert(num);
		return;
	}

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

		if (next_x >= 0 && next_x < 5 && next_y >= 0 && next_y < 5) {
			DFS(next_x, next_y, num + graph[next_x][next_y], cnt + 1);
		}
	}
}

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

	for (int i = 0; i < 5; i++) {
		for (int j = 0; j < 5; j++) {
			DFS(i, j, "" + graph[i][j], 0);
		}
	}

	cout << result.size();

	return 0;
}