백준 14500번 테트로미노 (삼성 SW 역량테스트 기출문제)

사용한 알고리즘: 브루스 포스, 구현...?


삼성 기출은 굉장히 구현문제가 많은 것 같습니다.
우리 화이팅 해 봅시다...!

우선 문제에서 주어진 폴리오미노(?)를 대칭, 회전 모두 가능하다 했기에
주어진 세가지 조건
1. 정사각형은 겹치지 않는다.
2. 도형은 모두 연결되어 있어야 한다.
3. 정사각형 끼리는 변으로 연결되어야 한다.
를 기준으로 생각했습니다.

먼저 (0,0) 사각형부터 끝 지점 까지 모든 사각형을 훑었습니다. (브루스 포스 - 완전탐색)
단 i 번째 사각형을 볼 때 좌,우,아래 사각형만 보고 사각형은 보지 않는 식으로 중첩을 최소화 하려고 했습니다.
함수를 하나 만들고 추가 블록 개수를 저장 (처음엔 4개) 하며 재귀형식으로 함수를 돌렸습니다.
(1) i 번째 사각형에서 추가 블록 개수가 (자신 제외)  i번째 사각형이 맞닿아 있는 (아직 쓰지않은) 사각형 개수보다 작은 경우
(2) 추가 블록 개수가 1 보다 큰경우 ( 추가 블록 개수가 1 인 경우는 (1)과정에서 이미 생각)
     아래 사각형으로 이동, 왼쪽 사각형으로 이동, 오른쪽 사각형으로 이동

위와같이 크게 2개의 과정으로 생각하여,
함수를 돌릴 때 과정(1) 의 경우는 그냥 노가다 해서 구했고,
(2) 의 경우는 재귀형태로 구해서
각 과정마다 구하고자 하는 최대값을 최신화 해 주었습니다.

푸는 방식 자체는 어렵지 않고, 다양한 풀이가 있을 거라고 생각됩니다.
(물론 저보다 훨씬 깔끔하게 푸는 분들도 많을 겁니다..!!)
포인트는 누가 실수를 안하고 구현을 하느냐 였던 문제인 것 같습니다.