문제 링크: 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'; | |
} | |
} |
'문제 해결 > 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 |