BaekJoon 2210번: 숫자판 점프

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

2210번: 숫자판 점프

풀이법

1) DFS를 활용하여 나올 수 있는 숫자의 합을 구하는 문제이다.

2) 겹치지 않게 visit 배열을 활용하여 겹치지 않게 처리하면 풀 수 있다.

3) 재귀와 stack을 활용할 수 있으나, stack으로 문제를 풀어보았다.

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <cstring>
#include <queue>
#include <set>
using namespace std;

int arr[5][5];
int vx[4] = { 1,0,0,-1 };
int vy[4] = { 0,1,-1,0 };
bool visited[1000000];
int ans = 0;
void dfs(int a, int b,int sum)
{
	stack < pair<int, pair<int, pair<int, int>>>> st;
	st.push({ a,{b,{sum,0}} });
	while (!st.empty())
	{
		int dx = st.top().first;
		int dy = st.top().second.first;
		int now = st.top().second.second.first;
		int cnt = st.top().second.second.second;
		st.pop();
		if (cnt == 5)
		{
			if (visited[now] == false)
			{
				visited[now] = true;
				ans++;
			}
			continue;
		}
		for (int i = 0; i < 4; i++)
		{
			int bx = dx + vx[i];
			int by = dy + vy[i];
			if (bx < 0 || by < 0 || by >= 5 || bx >= 5)
				continue;
			st.push({ bx,{by,{now * 10 + arr[bx][by],cnt + 1}} });
		}

	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	for (int i = 0; i < 5; i++)
	{
		for (int j = 0; j < 5; j++)
		{
			cin >> arr[i][j];
		}
	}
	for (int i = 0; i < 5; i++)
	{
		for (int j = 0; j < 5; j++)
		{
			dfs(i,j,arr[i][j]);
		}
	}
	cout << ans;
}