<baekjoon> 테트로미노

풀이

처음에는 가장 큰값을 무조건 포함해야 할 거같다는 생각을 했다. 하지만 꼭 가장 큰값을 포함한다고 최대값이 만들어 지지는 않는다.

 

5개의 테크로미노를 각 좌표에서 모든 경우의수를 고려하여 코드를 작성할려고 했지만 절대 불가능해보였다. 그래서 다시 잘 문제를 읽어보니 테크로미노는 무조건 4개를 연결시켜놓은 도형이다. 즉 DFS를 통해 3번만 타고 들어가면 어떤 도형이든 다 만들 수 있다는 것을 알게되었다. 

 

여기서 또다른 문제가 있었는데 'ㅗ' 모양의 도형은 순수 DFS로만 할려면 절대 불가능했다. 그래서 DFS를 통해서 마지막 좌표로 이동했을 시, 마지막 좌표의 값을 빼고 2번째 좌표의 위치로 이동하여 그 위치에서 4방탐색을 하였다. 이렇게 하면 'ㅗ' 모양을 만들 수 있다.

 

코드