[BOJ/백준 2210][C++] 숫자판 점프

문제

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

 

문제 내용

숫자판의 임의의 위치에서 시작하여, 5번 이동하면서 만들 수 있는 수의 개수를 출력하는 문제이다.

문제를 해결하기 위해 dfs를 사용했으며, 중복을 확인하기 위해 set을 사용했다.

 

문제 풀이

그렇게 어려운 문제는 아니다.

나는 dfs함수를 만들어서 재귀로 이 문제를 해결했다.

 

일단 5번을 이동하면 재귀를 끝낼 수 있도록 dfs()에 조건문을 넣어주었다.

다만, return을 하기 전에, set에 값을 집어넣어서 중복을 제거해주었다.

나중에 출력시 set.size() 해주면 된다.

 

dfs()에서 탈출 조건을 넘어간다면,  상하좌우로 이동을 하도록 코드를 짰다.

이때 x,y좌표가 범위를 벗어나는 것을 방지하기 위해 체크를 해주어야 한다.

또한 dfs()에서 인자를 넘길 때, 마지막 num은 우리가 만들 수 있는 수를 의미한다.

(그래서 num*10 +arr[px][py]을 넘겨주는 것. 해당 위치의 수를 계속 뒤에 붙여나가기 때문이다.)

 

코드

#include <iostream>
#include <algorithm>
#include <set>
using namespace std;

int arr[5][5];
set<int>ss;

//자리 이동
int xx[4] = { 1, -1, 0, 0 };
int yy[4] = { 0, 0, 1, -1 };

void dfs(int x, int y, int count, int num) {
	if (count == 5) {
		ss.insert(num);
		return;
	}

	for (int i = 0; i < 4; i++) {
		int px = x + xx[i];
		int py = y + yy[i];

		if (px < 0 || py < 0 || px>=5 || py>=5 ) continue;
		dfs(px, py, count + 1, num * 10 + arr[px][py]);
	}
}

int main() {
	//입력
	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++) //행 (y좌표)
		for (int j = 0; j < 5; j++) //열 (x좌표)
			dfs(j,i,0,arr[j][i]);
	
	//결과 출력
	cout << ss.size() << '\n';
}