격자판의 숫자 이어 붙이기

문제 : 2819
https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=4&contestProbId=AV7I5fgqEogDFAXB&categoryId=AV7I5fgqEogDFAXB&categoryType=CODE&problemTitle=&orderBy=SUBMIT_COUNT&selectCodeLang=ALL&select-1=4&pageSize=10&pageIndex=1

#include <vector>
#include <queue>
#include <set>
#include <string>


#define ARR 4

using namespace std;
int asw;
int map[ARR][ARR] = { 0, };
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,-1,0,1 };
string sType = "";
set<string> sCon;

void dfs(int starty, int startx, int depth, string s)
{
	if (depth == 7)
	{
		sCon.insert(s);
		return;// dfs종료 
	}

	for (int i = 0; i < ARR; i++)
	{
		int ny = starty + dy[i];
		int nx = startx + dx[i];
		if (nx >= 0 && nx < ARR && ny >= 0 && ny < ARR)
		{
			//s +=to_string(map[ny][nx]);
			dfs(ny, nx, depth + 1, s + to_string(map[ny][nx]));
		}
	}
}

int main() {
	int T; cin >> T;
	for (int test_case = 0; test_case < T; test_case++)
	{
		sCon.clear();
		for (int i = 0; i < ARR; i++)
		{
			for (int j = 0; j < ARR; j++)
			{
				int iTemp;	cin >> iTemp;
				map[i][j] = iTemp;
			}
		}

		
		for (int i = 0; i < ARR; i++)
		{
			for (int j = 0; j < ARR; j++)
			{
				string sStart = "";
				dfs(i, j, 0, sStart);
			}
		}

		int iResullt = sCon.size();

		printf("#%d %d\n", test_case + 1, iResullt);
	
		cout << endl;
	}
	return 0 ;
}

이 문제에서
dfs(ny, nx, depth + 1, s + to_string(map[ny][nx]));를
dfs(ny, nx, depth + 1, s += to_string(map[ny][nx]));해서
버그가 있었다.
DFS문제 스타일.
DFS에서 방문기록 체크 안하는 스타일의 문제

좋은 웹페이지 즐겨찾기