-
[BOJ - 14500] 테트로미노백준알고리즘 2020. 2. 24. 02:40
https://www.acmicpc.net/problem/14500
14500번: 테트로미노
폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다. 아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누
www.acmicpc.net
작년에 진짜 자바에서 빡구현으로 풀었던 문제다.
빡구현을 통해 속도를 챙길수 있지만, 코드작성 시간효율 측면에서 굉장히
비효율적이라는 생각이 든다.
경험에 의거해서 테트로미노의 도형들을 보았을때 떠올릴수 있는것은
凸같은 모양을 제외하고, 모든 도형이 시작 방향을 기준으로 딱 4번만 이동하면 되는 도형들이라는것이다.
그러한 도형들은 DFS하듯, 모든 영역을 탐색하면서 체킹할수있고 이러한 체킹을 기준으로 답을구할수있다.
또한, 이러한 도형을 제외한 나머지 하나의 도형은 모든 영역에서 다른 도형들 전부를 탐색한 뒤 포문 자체에서 해결하는 방식을 통해 탐색할수있다.
'백준알고리즘' 카테고리의 다른 글
[BOJ - 16933] 벽 부수고 이동하기3 (0) 2020.02.27 [BOJ - 16946] 벽 부수고 이동하기 4 (0) 2020.02.27 [BOJ - 18429] 근손실 (0) 2020.02.14 [BOJ - 4217] 신성 문자 (0) 2020.02.14 [BOJ - 14632] 고급 작품 (0) 2020.02.14