SWEA 2105번: [모의 SW 역량테스트] 디저트 카페

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5VwAr6APYDFAWu

SW Expert Academy

그림같은 맵이 있을 때, 같은 번호를 가진 node는 거치지 않고 마름모 모양으로 맵을 순회할 수 있는지 구하는 문제

디저트카페

순회 루트를 찾으면 되는데, BFS로 해줄 필요는 없이

그냥 이동 방향을 처음부터 내 맘대로(↖↗↘↙) 정한 뒤 최대 크기의 경로를 구해줬다

이동하면서 숫자 배열의 "현재 방문한 번호 인덱스"를 방문처리 해주면서 진행하면 된당

#include <cstdio>
#include <cstring>
int tc, n, map[21][21], ans, dx[] = { -1,1,1,-1 }, dy[] = { -1,-1,1,1 };
bool num[101];
typedef struct {
	int x, y;
}point;
point s;
bool safe(point p) { return p.x >= 0 && p.x < n && p.y >= 0 && p.y < n; }
void func(point cur,int dep, int sum) {
	if (dep > 3)return;
	point p = cur;
	p.x += dx[dep], p.y += dy[dep];
	while (safe(p) && !num[map[p.y][p.x]]) {
		if (dep == 3 && cur.x == s.x && cur.y == s.y) {
			if (sum > ans)ans = sum; break;
		}
		sum++;
		num[map[p.y][p.x]] = 1;
		func(p, dep + 1, sum);
		p.x += dx[dep], p.y += dy[dep];
	}
	if (p.x == s.x && p.y == s.y)
		if (sum > ans)ans = sum;
	cur.x += dx[dep], cur.y += dy[dep];
	while (!(cur.x == p.x && cur.y == p.y)) {
		num[map[cur.y][cur.x]] = 0;
		cur.x += dx[dep], cur.y += dy[dep];
	}
}
int main() {
	scanf("%d", &tc);
	for (int T = 1; T <= tc; T++) {
		ans = -1;
		scanf("%d", &n);
		for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)
			scanf("%d", &map[i][j]);

		for(int i=2;i<n;i++)
			for (int j = 1; j < n; j++) {
				memset(num, 0, sizeof(num));
				num[map[i][j]] = 1;
				s = { j,i };
				func({ j,i }, 0, 1);
			}

		printf("#%d %d\n", T, ans);
	}
	return 0;
}

+ 요즘드는 생각: 진작에 A+ 딸걸 ^^ 그랬다면 지금 면접준비만 하면 될텐데 😂