백준 알고리즘 풀이 14500번 - 테트로미노

https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net dfs로 풀수 있던 간단한 문제. 알고리즘 1. dfs로 ㅗ모양을 제외한 도형을 움직이면서 도형안에 들어가는 최댓값을 구한다. 2. ㅗ모양 탐지를 위해서 도형을 돌려본다. 3. 1,2번에 대해 맵 전체를 돌면서 최댓값을 찾는다. 시간 복잡도 dfs의 시간복잡도가 O(V+E)인데, 맵을 N X M 이므로 총 O(NXM(V+E)). 소스코드 #include using namespace std; int..

2021.07.05