[SWEA] 디저트 카페

문제링크
코드링크

• 문제요약

• 카페들 사이에는 대각선 방향으로 움직일 수 있는 길이 있다
• 디저트 카페투어는 어느 한 카페에서 출발하여 대각선 방향으로 움직이고
• 사각형 모양을 그리며 출발한 카페로 돌아와야한다. 또한 같은 종류의 디저트는 방문하지 않는다.
• 하나의 카페에서 디저트를 먹는 것도 안 된다.
• 왔던 길 을 다시 돌아가는 것도 안된다.
• 디저트를 가장 많이 먹을 수 있는 경로를 찾고 디저트 수를 출력, 먹을 수 없는 경우 -1 출력

• 문제접근
  - 처음 문제를 읽고 4방향 대각선만 탐색하면 될 줄 알았다. 그렇게 코드를 작성하다 테스트 케이스를 돌려보니 계속 오답이 나왔다. 대각선으로만 탐색하다보면 사각형모양이 아닌 경우도 나오게 되는데 이 경우도 카운팅이 되서 답이 더 크게 나옴

  • 그래서 사각형만 탐색하기 위해 방향 꺾는 횟수를 카운팅했다. 사각형은 총 네개의 선분을 가짐으로 네번의 방향전환이 필요하다.

• 회고
  - 문제에 대한 알고리즘이 떠올랐을 때 코드를 작성하기 전 5분 정도는 반례가 있는지를 생각하는 습관을 가지자