백준 14500 테트로미노
-
백준 14500 테트로미노Algorithm/BOJ 2020. 7. 15. 14:07
출처: www.acmicpc.net/problem/14500 분류: 완전 탐색 접근방식 주어진 5개의 테트로미노를 하나 놓을 때 테트로미노에 겹쳐지는 블록의 최대값이 얼마인지 구하는 문제입니다. 모든 경우를 다 체크하면 되겠지만 테트로미노는 회전 또는 대칭이 되기 때문에... 매우매우 귀찮습니다.. 😨 하지만 이 문제에는 귀찮음을 덜어줄 수 있는 법칙이 숨겨져 있습니다 :) 바로 ㅗ 모양을 제외한 테트로미노들은 한 점에서 dfs로 4개씩 탐색한 결과들입니다. 한 점에서 dfs로 4개의 블록을 고르면 4개의 테트로미노를 회전 대칭 시킨 모양안에 모두 포함됩니다! 대신 ㅗ 모양은 ㅗ ㅜ ㅏ ㅓ를 따로 찾아줘야 합니다. 해결방법 let nm = readLine()!.split(separator: " ").ma..