Waterbear

백준 14500: 테트로미노 본문

프로그래밍/알고리즘 문제풀이

백준 14500: 테트로미노

노간 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이므로 가능하다)

 

코드

 

 

'프로그래밍 > 알고리즘 문제풀이' 카테고리의 다른 글

백준 14503: 로봇청소기  (0) 2019.09.09
백준 13458: 시험감독  (3) 2019.09.09
07. WILDCARD  (0) 2019.05.27
06. FANMEETING  (0) 2019.05.27
05. FENCE  (0) 2019.05.13
0 Comments
댓글쓰기 폼