swea 2819. 격자판의 숫자 이어 붙이기(c++)

[문제]

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7I5fgqEogDFAXB

SW Expert Academy

[풀이]

dfs로 풀 수 있는 문제

중복을 피하기 위해 set을 사용하였다.

0부터 시작하는 숫자도 세야 하므로 자료형으로 string을 사용하였다.

 

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

int T;
char Map[4][4];
const int dx[] = { -1,1,0,0 };
const int dy[] = { 0,0,-1,1 };
set<string>s;

void dfs(int x, int y, int cnt, string num) {
	if (cnt == 7) {
		s.insert(num);
		return;
	}
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (nx < 0 || nx >= 4 || ny < 0 || ny >= 4)
			continue;
		dfs(nx, ny, cnt + 1, num + Map[nx][ny]);
	}
}

int main() {
	cin >> T;
	for (int i = 1; i <= T; i++) {
		s.clear();
		for (int x = 0; x < 4; x++) {
			for (int y = 0; y < 4; y++) {
				cin >> Map[x][y];
			}
		}
		for (int x = 0; x < 4; x++) {
			for (int y = 0; y < 4; y++) {
				dfs(x, y, 0, "");
			}
		}
		cout << '#' << i << ' ' << s.size() << '\n';
	}
	return 0;
}