27158번 - 펜토미노 스페셜 저지
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 (하단 참고) | 512 MB | 49 | 20 | 15 | 42.857% |
문제
폴리오미노란 크기가 $1 \times 1$인 정사각형을 둘 이상 이어서 붙인 평면도형이며, 다음과 같은 조건을 만족해야 한다.
- 서로 다른 두 정사각형 $A$, $B$가 인접하는 것은, 두 정사각형 $A$, $B$가 겹치지 않고 한 변을 공유하는 것으로 정의된다.
- 서로 다른 두 정사각형 $A$, $B$가 연결되어 있다는 것은, $A$와 $B$가 인접하거나, $A$와 인접하면서 $B$와 연결된 또 다른 정사각형 $C$가 존재한다는 것으로 정의된다.
- 폴리오미노를 이루는 정사각형 중 임의의 서로 다른 두 정사각형을 고르면 그 둘은 서로 연결되어 있다.
펜토미노는 정사각형 $5$개를 이어 붙인 폴리오미노를 의미한다. 펜토미노는 다음과 같이 $F$, $I$, $L$, $N$, $P$, $T$, $U$, $V$, $W$, $X$, $Y$, $Z$ 모양으로 $12$가지가 있다.
몽이는 크기가 $N \times M$인 직사각형 모양 보드 위에 $12$가지 펜토미노를 한 개씩 전부 놓으려고 한다. 보드는 크기가 $1 \times 1$인 정사각형 칸으로 나뉘어 있으며, 각각의 칸에는 $0$ 또는 $1$이 쓰여 있다. $0$이 쓰인 칸은 $60$개가 있다.
펜토미노를 놓을 땐 펜토미노의 각 정사각형이 반드시 보드의 한 칸을 정확하게 포함해야 하며, 펜토미노는 서로 겹칠 수 없다. 이때, 펜토미노는 $0$이 적힌 칸 위에만 놓을 수 있으며, $1$이 적힌 칸은 펜토미노가 덮을 수 없다. 또한, 각 펜토미노는 회전하거나 뒤집어서 보드에 올려놓을 수 있다.
위 조건을 만족하며 펜토미노 $12$개를 놓아 $0$이 적힌 모든 칸을 덮는 한 가지 경우를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 보드의 세로 크기 $N$과 가로 크기 $M$이 주어진다. ($3 \le N$, $M \le 100$)
둘째 줄부터 $N$개의 줄에 걸쳐 보드에 쓰여 있는 숫자 0 또는 1이 공백으로 구분되어 주어진다. $i$번째 줄의 $j$번째 숫자는 위에서부터 $i$번째 칸, 왼쪽에서부터 $j$번째 칸에 쓰여 있는 숫자이다.
$12$가지 펜토미노를 겹치지 않게 한 개씩 놓아 0이 쓰여 있는 칸을 모두 펜토미노로 덮을 수 있는 경우의 입력만 주어진다.
출력
첫째 줄부터 $N$개의 줄에 걸쳐 보드의 상태를 공백으로 구분하여 출력한다.
$i$번째 줄의 $j$번째 값은 위에서부터 $i$번째 칸, 왼쪽에서부터 $j$번째 칸의 상태이다. $i$번째 줄의 $j$번째 칸에는 펜토미노를 놓았다면 펜토미노의 종류를 나타내는 알파벳(F, I, L, N, P, T, U, V, W, X, Y, Z)을 출력하고, 펜토미노를 놓을 수 없는 칸이면 1을 출력한다.
만족하는 경우가 여러 가지라면 그중 아무거나 하나를 출력한다.
예제 입력 1
6 10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
예제 출력 1
N T T T X W W P P P N N T X X X W W P P L N T U X U F W Z Z L N Y U U U F F Z V L Y Y Y Y F F Z Z V L L I I I I I V V V
아래 그림은 예제 출력 1을 나타낸 모습이다.
예제 입력 2
8 8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
예제 출력 2
T I I I I I P P T T T N N X P P T N N N X X X P V V V 1 1 X F F V U U 1 1 F F Y V U W W Z Z F Y L U U W W Z Y Y L L L L W Z Z Y
아래 그림은 예제 출력 2를 나타낸 모습이다.
예제 입력 3
7 11 1 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1
예제 출력 3
1 P P P I I I I I F 1 V P P 1 T 1 X 1 F F F V 1 T T T X X X Z 1 F V V V 1 T 1 X 1 Z Z Z W 1 L L L L U U U 1 Z W W L 1 Y 1 U 1 U N N 1 W W Y Y Y Y N N N 1
아래 그림은 예제 출력 3을 나타낸 모습이다.
예제 입력 4
8 11 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
예제 출력 4
V V V I I I I I U U U V 1 1 1 1 1 1 1 U X U V 1 1 1 1 1 1 1 X X X Y 1 1 1 1 1 1 1 F X N Y 1 1 1 1 1 1 1 F F N Y Y W Z Z P T F F N N Y W W Z P P T T T N L W W Z Z P P T L L L L
아래 그림은 예제 출력 4를 나타낸 모습이다.
예제 입력 5
8 11 1 1 0 0 1 1 1 0 0 1 1 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 0 1 1 0 0 0 0 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 1 1 1 1 0 1
예제 출력 5
1 1 W W 1 1 1 U U 1 1 1 W W F T T T U Z Z 1 1 W F F F T V U U Z 1 P P 1 1 F T V 1 1 Z Z P P 1 1 V V V 1 1 L N P X Y Y Y Y L L L L N X X X Y I I I I I N N 1 X 1 1 1 1 1 1 1 N 1
아래 그림은 예제 출력 5를 나타낸 모습이다.
예제 입력 6
11 10 1 1 1 0 0 0 0 1 1 1 1 1 0 0 1 1 0 0 1 1 1 1 0 0 1 1 1 0 1 1 0 0 0 0 1 1 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 1 1 1 0 1 1 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 1 1 0 0 1 1 0 0 1 1
예제 출력 6
1 1 1 F F W W 1 1 1 1 1 F F 1 1 W W 1 1 1 1 P F 1 1 1 W 1 1 L L P P 1 1 U U X 1 L T P P 1 1 U X X X L T T T 1 1 U U X 1 L T N N 1 1 1 I 1 1 V V V N N N Y I 1 1 1 1 V Z Z Y Y I 1 1 1 1 V Z 1 1 Y I 1 1 1 1 Z Z 1 1 Y I 1 1
아래 그림은 예제 출력 6을 나타낸 모습이다.
출처
- 문제를 검수한 사람: bamgoesn, tlsdydaud1, tony9402, utilforever, wider93
- 문제를 만든 사람: wapas
시간 제한
- Go: 1 초
- Go (gccgo): 1 초
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호