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

문제

---

 

문제 풀어보기

 

 

풀이

---

 

이 문제는 완전 탐색 문제입니다.

 

 

 

우선 탐색을 시작할 시작점의 좌표를 정하는 FOR문 두 개

두 대각선의 길이를 정하는 FOR문 두 개를

메인에서 정해줍니다.

 

그리고 그 조건으로 문제를 푸는 거죠.

 

 

허접하지만 이해를 돕기 위해 그림을 그려보면

저는 시작점을 왼쪽 끝에 있는 파란 동그라미로 잡았습니다.

 

 

시작점을 어느 점으로 정 하냐에 따라 순서가 조금씩 달라질 수 있습니다.

그리고 두대 각선의 길이는 빨간색선으로 표시했습니다.

 

 

굉장히 유사한 문제를 가져왔습니다.

 

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

17779번: 게리맨더링 2

 

코드

---

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;
#define safe(x,y) x>=n || x<0 || y<0 || y>=n

//int dx[] = { 1,-1 ,0,0 };
//int dy[] = { 0,0,1,-1 };
// 아래 위 오른쪽 왼쪽

int dx[] = { -1, 1, 1, -1 };
int dy[] = { 1, 1, -1 , -1 };
// 대각선

int n;
int arr[25][25];
int ans;

void go(int i, int j, int d1 , int d2) {
	int x = i;
	int y = j;
	vector<bool> check(101, false);
	check[arr[i][j]] = true;

	int sum = 1;

	for (int k = 0; k < 4; k++) {
		if (k % 2 == 0) { // d1
			for (int r = 0; r < d1; r++) {
				x += dx[k];
				y += dy[k];
				if (safe(x, y) || check[arr[x][y]]) return;
				check[arr[x][y]] = true;
				sum += 1;
			}
		}
		else {
			for (int r = 0; r < d2; r++) {
				x += dx[k];
				y += dy[k];
				if (x == i && y == j) break; // 다 돌았다면
				if (safe(x, y) || check[arr[x][y]]) return;
				check[arr[x][y]] = true;
				sum += 1;
			}
		}


	}

	if (sum > ans) ans = sum;

}

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

	int T;

	cin >> T;
	for (int t = 1; t <= T; t++) {
		cin >> n;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				cin >> arr[i][j];
			}
		}

		ans = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				for (int r = 1; r <= n; r++) {
					for (int c = 1; c <= n; c++) {
						go(i, j, r, c);
					}
				}
			}
		}


		if (ans == 0) ans = -1;
		cout << "#" << t << ' ';
		cout << ans << endl;

	}




	return 0;
}