C++ / 2210 / 숫자판 점프 ( 깊이 우선 탐색 )

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

문제 요약

5×5 크기의 숫자판이 있습니다.

각각의 칸에는 숫자(digit, 0부터 9까지)가 적혀 있습니다.

이 숫자판의 임의의 위치에서 시작해서, 인접해 있는 네 방향으로 다섯 번 이동하면서, 각 칸에 적혀있는 숫자를 차례로 붙이면 6자리의 수가 됩니다.

이동을 할 때에는 한 번 거쳤던 칸을 다시 거쳐도 되며, 0으로 시작하는 000123과 같은 수로 만들 수 있습니다.

숫자판이 주어졌을 때, 만들 수 있는 서로 다른 여섯 자리의 수들의 개수를 구하는 프로그램을 작성해야합니다.

문제 풀이

1. 5 * 5 배열을 만들어 숫자들을 입력받습니다.

2. 각 숫자별로 dfs탐색을 합니다.

3. 탐색은 4방향으로 하면서, 각 숫자들을 벡터배열에 추가합니다.

4. 벡터배열의 사이즈가 6이 되면 정답 배열이 비어있을 경우엔 바로 추가후 개수를 셉니다.

정답 배열이 비어있지 않으면 정답 배열에 들어있는 수열들과 비교하여 같은 수열일 없을 경우에만 저장하고 개수를 세고 반환합니다.

5. 재귀함수가 반환되면 현재 수열 추가 한걸 없애줍니다. ( 다른 방향 탐색 후 새로운 수열을 만들기 위해 ) 

6. 탐색을 마치고 개수를 출력합니다.

주의할 점

6자리의 수열이 되도록 주의해야합니다.

코드

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

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

bool visit[100][100];
vector<vector<int>>v, ans;
vector<int>t;
int cnt = 0;

void dfs(int y, int x)
{
	// 수열이 6개 채워지면
	if (t.size() == 6)
	{
		int check = 0;
		// 현재 저장되어 있는 수열이 있을 경우
		if (!ans.empty())
		{
			// 저장된 수열들과 현재 수열이 같은지 비교 
			for (int i = 0; i < static_cast<int>(ans.size()); i++)
			{

				// 이미 있는 수열인 경우
				if (t == ans[i])
				{
					check = 1;
				}

			}
			// 수열이 없는거면 새로 저장
			if (!check)
			{
				cnt++;
				ans.push_back(t);
			}

		}
		else// 저장된 수열이 없는 경우엔 저장
		{
			cnt++;
			ans.push_back(t);
		}
		return;
	}
	for (int i = 0; i < 4; i++)
	{
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (ny >= 5 || ny < 0 || nx >= 5 || nx < 0)
		{
			continue;
		}
		t.push_back(v[ny][nx]);
		dfs(ny, nx);
		t.pop_back();
	}
}

int main()
{
	v.resize(5, vector<int>(5));
	for (int i = 0; i < 5; i++)
	{
		for (int j = 0; j < 5; j++)
		{
			cin >> v[i][j];
		}
	}
	for (int i = 0; i < 5; i++)
	{
		for (int j = 0; j < 5; j++)
		{
			dfs(j, i);
		}
	}

	cout << cnt;
	return 0;
}

반응형

예제

1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 2 1
1 1 1 1 1

결과