Study/Algorithm
백준 14500: 테트로미노
jhin.lee
2019. 9. 9. 12:58
문제
https://www.acmicpc.net/problem/14500
14500번: 테트로미노
폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다. 아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누
www.acmicpc.net
풀이
어려운 문제는 아니지만 실수하기 쉬운 문제다.
테트로미노의 경우의 수가 19개 있는데 햇갈리지 않고 정확하게 코딩하면 된다.
이런 류의 문제를 풀 때는 기준점을 잘 잡으면 쉽게 풀수 있는데 보통 왼쪽이나 위를 기준으로 잡으면 좀 편하다.
나는 밖으로 삐져나오는 녀석들을 처리해 주기가 귀찮아서 전체 맵을 -9999로 3칸씩 둘러 싸 놨다. (위는 제외)
이렇게 하면 밖으로 나온 인덱스를 더해도 -값이 나오므로 최대값이 되지 않는다. (각각이 최대 1000이므로 가능하다)
코드