31722번 - 산수화 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 101 | 47 | 43 | 53.086% |
문제
윤이의 취미는 그림 그리기이다. 어느 날, 학교 뒷산을 보고 영감을 받은 윤이는 산수화 한 장을 그려 내었다. 산수화는 $N$행 $M$열의 격자 모양이며, 각 칸은 검은색 또는 흰색으로 칠해져 있다.
윤이는 산수화를 포닉스와 달구에게 선물하기로 했다. 그러나 그림은 한 장뿐이었고, 포닉스와 달구는 누가 그림을 가져야 하는지에 대한 토론을 시작했다. 토론은 쉽게 끝나지 않았는데 그 이유는 포닉스와 달구가 생각하는 좋은 산수화의 기준이 서로 다르기 때문이었다.
달구는 산이 많은 산수화를 좋은 산수화라고 생각하며, 포닉스는 호수가 많은 산수화를 좋은 산수화라고 생각한다. 산과 호수의 정의는 각각 아래와 같다. $(i,j)$는 $i$번째 행 $j$번째 열에 해당하는 칸을 의미한다.
- $a\le x,|a-x|+|b-y|\le d-1$를 만족하는 $(a,b)$가 모두 검은색이라면 이를 $(x,y)$를 중심으로 하고 크기가 $d$인 산이라 한다. 이때 $d$는 $1$ 이상 $\min(y,M-y+1,x)$ 이하의 정수여야 한다.
- $x\le a\le x+d-1,y\le b\le y+d-1$을 만족하는 $(a,b)$가 모두 흰색이라면 이를 $(x,y)$를 왼쪽 위 꼭짓점으로 하고 크기가 $d$인 호수라 한다. 이때 $d$는 $1$ 이상 $\min(N-x+1,M-y+1)$ 이하의 정수여야 한다.
위 그림의 경우, $(3,2)$를 중심으로 하고 크기가 $2$인 산과 $(1,3)$을 왼쪽 위 꼭짓점으로 하고 크기가 $2$인 호수가 있다.
윤이는 친구들의 토론을 멈추기 위해 $1$부터 $N$까지의 모든 $i$에 대해 크기가 $i$인 산의 개수와 호수의 개수를 직접 구해 주려 한다. 윤이를 도와 문제를 해결해 보자.
입력
첫째 줄에 산수화의 행의 수 $N$과 열의 수 $M$이 공백으로 구분되어 주어진다. $(1 \le N, M \le 2000)$
둘째 줄부터 $N$줄에 걸쳐 산수화가 주어진다. $i+1$번째 줄에는 산수화의 $i$번째 행을 나타내는 길이가 $M$인 문자열이 주어진다. 모든 문자열은 # 또는 . 으로 구성된다. #은 검은색, .은 흰색을 의미한다.
출력
첫째 줄에 크기가 $i$인 산의 개수를 나타내는 $N$개의 정수 $A_1, A_2, \cdots, A_N$을 공백으로 구분해 출력한다.
둘째 줄에 크기가 $i$인 호수의 개수를 나타내는 $N$개의 정수 $B_1, B_2, \cdots, B_N$을 공백으로 구분해 출력한다.
예제 입력 1
3 4 .... .#.. ###.
예제 출력 1
4 1 0 8 1 0
예제 입력 2
6 5 ..... ..... ..... ..#.. .###. #####
예제 출력 2
9 4 1 0 0 0 21 10 3 0 0 0
출처
University > UNIST-DGIST-POSTECH > 2024 UNIST-DGIST-POSTECH 연합 프로그래밍 경진대회 (2024 UDPC) > Junior Division H번
University > UNIST-DGIST-POSTECH > 2024 UNIST-DGIST-POSTECH 연합 프로그래밍 경진대회 (2024 UDPC) > Open Contest H번
- 문제를 만든 사람: leo020630
- 문제를 검수한 사람: 99asdfg, hyperbolic, lky7674, mjhmjh1104, nick832, queued_q, slah007, utilforever
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호