목록14500 (1)

설모의 기록

[백준 14500] 테트로미노

이 문제는 4개짜리 테트로미노 블럭을 주어진 이차원 배열에 놨을 때 배열의 값의 합이 최대가 되는 값을 구하는 문제입니다. 폴리오미노의 조건은 아래와 같습니다.정사각형은 서로 겹치면 안된다.도형은 모두 연결되어 있어야 한다.정사각형의 꼭지점끼리 연결되어 있어야 한다. 즉, 변과 꼭지점이 맞닿아 있으면 안된다.이 때, 정사각형 4개를 이어붙인 폴리오미노를 테트로미노라 하고 아래의 그림과 같이 5가지 종류입니다. 저도 처음에는 '5개를 어떻게 회전하지.. 4*4배열을 생성해서 그 배열을 회전해야하나..' 하는 함정에 빠졌습니다. 이것을 어떻게 해결하냐가 관건입니다. 이 문제는 dfs로 간단하게 풀리는 문제입니다. 'ㅜ' 블럭을 제외한 4개의 블럭은 한번에 그릴 수 있죠? 다시 말하면 dfs로 한번에 탐색할 ..
알고리즘 2018. 4. 15. 20:07
이전 Prev 1 Next 다음