Baekjoon 14500 테트로미노 JAVA

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

14500번: 테트로미노

https://github.com/JUNGSOONIL/JAVA/blob/main/BAEKJOON%2014500

GitHub - JUNGSOONIL/JAVA: JAVA 소스 코드

​

해당 문제는 테트리스에 나오는 도형 모양 중에서 map에서 해당 도형 모양만큼

값을 더했을 때 그중 최댓값을 구하는 문제다.

​

처음에 문제를 보고 그냥 싹 완탐으로 구현하면 되겠다 생각했는데,

암만 생각해도 너무 비효율적인 거 같았고

방법이 있을 거 같았는데, 결국 방법을 찾지 못해 구글링해 보니

​

ㅗ 모양을 제외하곤 dfs 한 번으로 모두 체크가 가능한 것을 확인했다.

​

약간 내가 느꼈던 건 순조부랑 비슷한 느낌이었다.

​

dfs에서는 크기가 4가 되면 최댓값을 증가시켜주고 그렇지 않을 경우 계속 진행하는데,

이게 이제 처음에는 위로 4칸다 가고 그다음에 3칸에 아래 한 칸 가면 방문했으니 이제 3칸에 왼쪽 가고 3칸에 오른쪽 가고 이런 식으로 방문하면 모양을 모두 방문할 수 있다.

​

이후 ㅗ 모양에 대해서만 따로 코드를 작성해 주면 해결 가능하다.

 

흰색 부분은 모든 모양에 포함된다.