[SWEA 2105] 디저트 카페

https://swexpertacademy.com/main/solvingProblem/solvingProblem.do

SW Expert Academy

#include <cstdio>
#include <cstring>
#include <set>
int T;
int N;
int board[20 + 2][20 + 2];
int visited[20 + 2][20 + 2];
int ans = 1;

std::set<int> S;


void init()
{
	memset(board, 0, sizeof(board));
	ans = 1;
	N = 0;
}

void input()
{
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &board[i][j]);
		}
	}
}


bool chk_diff(int real_cnt)
{
	S.clear();

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (visited[i][j]) S.insert(board[i][j]);
		}
	}
	if (S.size() == real_cnt) return true;	
	return false;
}



void DFS(int sx, int sy, int x, int y, int p, int cnt, int move)
{
	// dir
	static int dir_x[4] = { 1, 1, -1, -1 };
	static int dir_y[4] = { 1, -1, -1, 1 };

	if (move == 4) return;

	if (cnt >= 4 && sx == x && sy == y) {
		int real_cnt = cnt - 1;
		if (!chk_diff(real_cnt)) return;
		if (ans < real_cnt) ans = real_cnt;
		return;
	}

	int nx = 0;
	int ny = 0;

	// 같은 방향으로 이동 
	nx = x + dir_x[p];
	ny = y + dir_y[p];
	if (nx >= 0 && nx <= N - 1 && ny >= 0 && ny <= N - 1 && visited[nx][ny] == 0) {
		visited[nx][ny] = 1;
		DFS(sx, sy, nx, ny, p, cnt + 1, move);
		visited[nx][ny] = 0;
	}

	// 다음 방향으로 이동 
	nx = x + dir_x[(p + 1) % 4];
	ny = y + dir_y[(p + 1) % 4];
	if (nx >= 0 && nx <= N - 1 && ny >= 0 && ny <= N - 1 && visited[nx][ny] == 0) {
		visited[nx][ny] = 1;
		DFS(sx, sy, nx, ny, (p + 1) % 4, cnt + 1, move + 1);
		visited[nx][ny] = 0;
	}
}



void Flood_Fill()
{
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			memset(visited, 0, sizeof(visited));
			DFS(i, j, i, j, 0, 1, 0);
		}
	}
}


int main()
{
	scanf("%d", &T);
	for (int t = 1; t <= T; t++) {
		init();
		input();
		Flood_Fill();
		if (ans == 1) printf("#%d %d\n",t, -1);
		else printf("#%d %d\n",t, ans);
	}
	return 0;
}

DFS 돌릴때마다 visited 배열 백업하고 원복하니까 시간초과 났다. 

20 * 20 맵이라서 생각없이 했는데 역시나 시간초과... DFS 쓰면 TLE 진짜 신경써야 겠다... 

앞으로 갈 경로는 1로 표시하고, DFS 돌아오면서 0 으로 바꿔주면 된다. 

 

동일한 가게에 방문했는지 안했는지 판단하는 것은 set을 사용했다. 

현재까지 지나온 칸의 개수 - 1 (시작 좌표는 2번 방문함)과 S.size()를 비교하여 같으면 true를 리턴하여 ans 값을 갱신해주고, 다르면 false 리턴하게끔 구현했다.