백준(BOJ) 2210번 숫자판 점프

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

2210번: 숫자판 점프

 

풀이 :

 

0,0좌표부터  ~ 4.4 좌표까지 하나씩 시도해보자. 중복이 없으니 방문표시를 하는 배열은 없다.

 

자기자신 + 5번 이므로 총 6번을 갔다면 set에 저장하자. set은 중복 저장을 막는 용도로 사용하였다.

 

중복을 제외한 총 개수를 출력하면 답이된다.

 

 

	#include <iostream>
	#include <vector>
	#include <string>
	#include <set>
	using namespace std;
	int board[5][5];
	int dy[4] = { 1,-1,0,0 };
	int dx[4] = { 0,0,1,-1 };
	set<int> ret;
	void solve2(int y, int x, int ans, int len)
	{
	if (len == 6)
	{
	ret.insert(ans);
	return;
	}
	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;
	solve2(ny, nx, ans * 10 + board[ny][nx], len + 1);
	}
	}
	int main()
	{
	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) {
	solve2(i, j, board[i][j], 1);
	}
	cout << ret.size() << "\n";
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub