테트로미노

https://www.acmicpc.net/problem/14500

삼성 기출문제이다. 매우 어려운 문제였다.

처음에, 도형의 모든 경우의 수를 하나 하나 놓아봐서 최대값을 구해야하는지 생각했다.

하지만, DFS로 해결할 수 있다.

풀이

다음 그림과 같이 DFS를 이용하여 최대한 깊이 탐색한다.

ㅗ 모양을 제외한 모양은 DFS로 탐색이 가능하다. 4개의 탐색(깊이 3) 까지 마쳤을 때, 최대값을 계산한다.

ㅗ 모양은 현재 위치를 기준으로 동, 서, 남, 북을 조사하여 4개 중에 최소 값을 빼서 최대값을 계산할 수 있다.

다음 그림처럼 A를 기준으로 B, C, D, E 네 방향을 탐색한다.

만약에, E가 B, C, D, E 네 개 중에 최소값이라면, 다음 그림처럼 E를 제외하고 합을 구한다.