문제

SWEA_2105_디저트_카페

요약

N개의 2차원 배열 안에 1~100까지의 숫자들이 주어질 때, 대각선 방향으로 움직이면서 만들 수 있는 모든 사각형 중 사각형의 구성 숫자들이 곂치지 않는 사각형을 구성하는 칸의 최대 개수!

접근

이걸 사각형 모양을 만들어야하니까 N-Queen처럼 하나씩 놔보면서 사각형이 만들어지는지를 확인해간다 생각하면 백트래킹이 떠오른다!

알고리즘

격자 그래프로 생각하고, dfs를 활용한 백트래킹!

최종 코드

어려웠던 점

백트래킹이 아직 익숙하지 않아서 visited 관리를 못해서 못풀었다.
문제를 푸는데 총 3시간이 걸렸다.
대각선으로 사각형 조합을 만드는건 알겠는데, 이를 어떻게 구현해야하는지 도저히 감이 안와서 이것부터 AI에게 구현 방식에 대해 아이디어를 도움을 받았다.
➡️ dr, dc를 대각으로 돌리는건 맞는데, 백트래킹으로 꺾었을 때, 꺾지 않았을 때로 사각형 조합이 만들어지는지를 확인하면서 나아가야한다!

깨달은 점

• 디버거를 쓰는게 정말 중요하다! (이걸로 static 초기화 안한거 찾았다...)