본문 바로가기
문제 해결/SWEA

[SWEA] 2105. 디저트 카페

by 자잘 2019. 12. 28.

 문제 링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5VwAr6APYDFAWu

 

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

swexpertacademy.com

  시뮬레이션 문제입니다. 간단하게 문제를 설명드리면 정사각형 지역에 디저트를 파는 카페들이 있습니다. 각 카페에서 판매하는 디저트는 숫자로 나타냅니다. 지역에는 대각선으로 이동할 수 있는 길이 있고 대각선으로 이동하면서 사각형을 그리며 출발한 카페로 돌아와야합니다. 하나의 카페에서만 먹는 것도 허용되지 않고 같은 디저트를 먹는 것도 허용되지 않습니다. 그리고 또 왔던 길을 돌아가는 것도 허용하지 않습니다. 

 

 기본적으로 저의 풀이 방식은 모든 지점에서 시계 방향으로 탐색하게 됩니다. 어차피 어떤 방향으로 탐색을 하든 처음 지점으로 돌아오면 되므로 탐색 순서는 중요하지 않을 것 같습니다. 여튼 탐색을 하기 전에 사각형의 꼭지점이 되는 지역들이 지역 범위내에 있는지를 검사했습니다. 직접 해보시면 아시겠지만 정사각형에서 대각선으로만 이동하면서 원위치로 돌아오려면 무조건 직사각형이 됩니다. 이를 바탕으로  각 꼭지점을 계산하면 됩니다.(check_rec 함수)

 

 두번째로는 이제 꼭지점들이 지역내에 있으면 이를 바탕으로 탐색을 시작합니다. 위의 조건들을 만족하는지 여부를 판단하면서 탐색을 하면 됩니다. (dessert_route 함수) 자세한 내용은 코드를 보시면 이해가 되실겁니다.

 

#include<iostream>
#include<algorithm>
using namespace std;
int n, ans, tc;
int map[20][20];
int dx[4] = { 1,-1,-1,1 };
int dy[4] = { 1,1,-1,-1 };
bool InRange(int y, int x)
{
return 0 <= x && x < n && 0 <= y && y < n;
}
int dessert_route(int y, int x, int length1, int length2)
{
bool visited[101] = { false, };
int l1 = length1;
int l2 = length2;
int yy = y;
int xx = x;
int cnt = 0;
while(l1--)
{
if (visited[map[yy][xx]])
{
return -1;
}
visited[map[yy][xx]] = true;
cnt++;
yy += dy[0];
xx += dx[0];
}
l2 = length2;
while (l2--)
{
if (visited[map[yy][xx]])
{
return -1;
}
visited[map[yy][xx]] = true;
cnt++;
yy += dy[1];
xx += dx[1];
}
l1 = length1;
while (l1--)
{
if (visited[map[yy][xx]])
{
return -1;
}
visited[map[yy][xx]] = true;
cnt++;
yy += dy[2];
xx += dx[2];
}
l2 = length2;
while (l2--)
{
if (visited[map[yy][xx]])
{
return -1;
}
visited[map[yy][xx]] = true;
cnt++;
yy += dy[3];
xx += dx[3];
}
return cnt;
}
//해당 루트를 직접 돌아봄
bool check_rec(int y, int x, int length1, int length2)
{
return InRange(y + length1 * dy[0], x + length1 * dx[0]) && InRange(y + length2 * dy[1], x + length2 * dx[1])
&& InRange(y + length1 * dy[0] + length2 * dy[1] , x + length1 * dx[0] + length2 * dx[1]);
}
//사각형을 구성할 수 있는지 여부를 검사
int main(void)
{
cin >> tc;
for (int t = 1; t <= tc; t++)
{
cin >> n;
ans = -1;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
cin >> map[i][j];
}
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
for (int p = 1; p < n - 1; p++)
{
for (int q = 1; q <= n - p - 1; q++)
{
if (check_rec(i, j, p, q))
{
ans = max(ans, dessert_route(i, j, p, q));
}
}
}
}
}
cout <<'#'<<t<<' '<< ans << '\n';
}
}
view raw [SWEA] 2105.cpp hosted with ❤ by GitHub

'문제 해결 > SWEA' 카테고리의 다른 글

[SWEA] 2115. 벌꿀채취  (0) 2019.12.30
[SWEA] 2112. 보호필름  (0) 2019.12.30
[SWEA] 1953. 탈주범 검거  (0) 2019.12.28
[SWEA] 1952. 수영장  (0) 2019.12.27
[SWEA] 1949. 등산로 조성  (0) 2019.12.27