[SWEA] 2105. 디저트 카페

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

SW Expert Academy

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

 

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

 

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