백준 2210 숫자판 점프 C++

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

2210번: 숫자판 점프

5 x 5 숫자판을 돌아다니면서 6자리 수를 만들 수 있는 경우의 수를 구하는 문제입니다.

조건으로 중복해서 같은 위치를 지날 수 있음에 주의해야 합니다.

 

판 자체가 5 x 5로 작은 편이므로 특별한 조건 없이 bfs를 진행할 수 있습니다.

bfs를 통해 각 위치를 출발점으로 6자리를 계속 만들어가면서 6자리가 만들어졌을 때 set에 넣습니다.

그러면 set은 중복되는 경우가 없기 때문에 set의 크기가 정답입니다.

 

코드는 다음과 같습니다.

#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#include <string>

using namespace std;

int numbers[5][5];
int dy[4] = { 1,-1,0,0 };
int dx[4] = { 0,0,1,-1 };
set<int> s;

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

void bfs(int y, int x)
{
	queue<pair<string, pair<int, int>>>q;
	int num = numbers[y][x];
	string start = "";
	start += '0' + num;
	q.push({ start, {y, x} });

	while (!q.empty()) {
		string str = q.front().first;
		int y = q.front().second.first;
		int x = q.front().second.second;
		q.pop();

		if (str.size() == 6) {
			s.insert(stoi(str));
			continue;
		}

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

			if (ny < 0 || ny >= 5 || nx < 0 || nx >= 5)
				continue;

			string str2 = str;
			str2 += '0' + numbers[ny][nx];
			q.push({ str2, {ny, nx} });
		}
	}
}

int main()
{
	init();
	for (int y = 0; y < 5; y++) {
		for (int x = 0; x < 5; x++) {
			bfs(y, x);
		}
	}

	cout << s.size();
}