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

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

SW Expert Academy

 

FIFO를 위한 Queue 의 응용 문제정도로 보인다.

입력에 대한 처리의 수월하게 해 줄 자료구조를 우선적으로 떠올려 보는 습관을 가져야겠다.

#include <iostream>
#incluse <queue>
using namespace std;

int N, cnt=-1;
int map[21][21];
int visit[21][21];
int dx[] = { 1,1,-1,-1 };
int dy[] = { 1,-1,-1,1 };

void search(int x, int y, int R, int L) {

	if ((R + L)*2 < cnt) return;
	
	queue<pair<int, int>> q;
	int Kinds[101] = {};
	int ct = 0;

	q.push(make_pair(x, y));
	for (int i = 0; i < R; i++) {
		x += dx[0];
		y += dy[0];
		q.push(make_pair(x, y));
	}
	for (int i = 0; i < L; i++) {
		x += dx[1];
		y += dy[1];
		q.push(make_pair(x, y));
	}
	for (int i = 0; i < R; i++) {
		x += dx[2];
		y += dy[2];
		q.push(make_pair(x, y));
	}
	for (int i = 0; i < L; i++) {
		x += dx[3];
		y += dy[3];
		q.push(make_pair(x, y));
	}
	x = q.front().first;
	y = q.front().second;
	int r, c;
	while (!q.empty()) {
		r = q.front().first;
		c = q.front().second;

		int num = map[r][c];
		if (Kinds[num] == 1) {
			break;
		}
		if (r <1 || r>N || c < 1 || c > N) {
			break;
		}
		Kinds[num] = 1;
		ct++;
		q.pop();
	}
	// 다르다면 fail
	if (x == r && y == c) {
		cnt = (R + L) * 2;
	}
}

int main(int argc, char** argv)
{
	int test_case;
	int T;
	//freopen("input.txt", "r", stdin);
	cin>>T;
	for(test_case = 1; test_case <= T; ++test_case)
	{
		cnt = -1;
		/////////////////////////////////////////////////////////////////////////////////////////////
		cin >> N;
		for (int nh = 1; nh <= N; nh++)
			for (int nw = 1; nw <= N; nw++)
				cin >> map[nh][nw];
		for (int i = 2; i < N; i++)
			for (int j = 1; j < N; j++) {
				for (int n = N - j; n >= 1; n--) {

					for (int r = 1; r < n; r++) {
						int l = n - r;
						search(j, i, r, l);
					}
				}
			}
		cout <<"#"<<test_case<<" " <<cnt;
        printf("\n");
		/////////////////////////////////////////////////////////////////////////////////////////////
	}
	return 0;
}