취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 2210번 문제인 숫자판 점프이다.
문제는 아래 링크를 확인하자.

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

각 칸을 시작지점으로 하여 점프를 5번 하는 모든 움직이는 경우를 탐색하자.

시작점이 25곳, 점프 5번을 하는 방법은 4^5 = 1024가지이므로 제한시간 내로 탐색을 충분히 마칠 수 있다.

위의 탐색을 구현할 때 숫자판을 벗어나는 점프를 하지 않아야한다는 점에 유의하자.

set을 이용하면 서로 다른 문자열의 개수를 쉽게 구할 수 있다.

아래는 제출한 소스코드이다.

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

char board[5][5];
set<string> st;

string str = "";
int dr[4] = { 1,-1,0,0 };
int dc[4] = { 0,0,1,-1 };

void func(int r, int c, int len) {
	if (len == 6) st.insert(str);
	else {
		for (int i = 0; i < 4; i++) {
			int rr = r + dr[i], cc = c + dc[i];
			if (rr == -1 || rr == 5 || cc == -1 || cc == 5) continue;
			str.push_back(board[rr][cc]);
			func(rr, cc, len + 1);
			str.pop_back();
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	for (int r = 0; r < 5; r++) {
		for (int c = 0; c < 5; c++) {
			cin >> board[r][c];
		}
	}

	for (int r = 0; r < 5; r++) {
		for (int c = 0; c < 5; c++) {
			str.push_back(board[r][c]);
			func(r, c, 1);
			str.pop_back();
		}
	}

	cout << st.size();
}