레이팅 미적용농부 존이 아이스크림 사업에 뛰어든다! 그는 아이스크림 덩어리를 만들어내는 기계를 만들었지만, 아쉽게도 모양이 다소 불규칙하게 나온다. 그는 기계를 최적화하여 출력되는 모양을 더 그럴듯하게 만들고 싶어한다.
기계가 출력하는 아이스크림의 배치는 다음과 같이 \(N \times N\) 격자 (\(1 \leq N \leq 1000\))로 나타낼 수 있다.
##....
....#.
.#..#.
.#####
...###
....##
각 '.' 문자는 빈 공간을, 각 '#' 문자는 \(1 \times 1\) 정사각형의 아이스크림 칸을 나타낸다.
안타깝게도 기계는 현재 상태가 좋지 않아서, 서로 분리된 여러 개의 아이스크림 덩어리를 만들어낼 수도 있다 (위 그림에는 두 개가 있다). 덩어리 안의 어떤 아이스크림 칸에서든 북, 남, 동, 서 방향으로 인접한 아이스크림 칸으로 반복해서 이동하여 다른 모든 아이스크림 칸에 도달할 수 있으면, 그 아이스크림 덩어리는 연결되어 있다고 한다.
농부 존은 넓이가 가장 큰 아이스크림 덩어리의 넓이와 둘레를 알고 싶어한다. 덩어리의 넓이는 그 덩어리에 속한 '#' 문자의 개수이다. 넓이가 가장 큰 덩어리가 여러 개라면, 그중 가장 작은 둘레를 알고 싶어한다. 위 그림에서 작은 덩어리는 넓이 2, 둘레 6이고, 큰 덩어리는 넓이 13, 둘레 22이다.
덩어리 가운데에 "구멍" (아이스크림으로 둘러싸인 빈 공간)이 있을 수 있다는 점에 유의하자. 그런 경우 구멍과의 경계도 덩어리의 둘레에 포함된다. 덩어리가 다른 덩어리 안에 중첩되어 나타날 수도 있으며, 이 경우 서로 다른 덩어리로 취급한다. 예를 들어 다음 경우에는 넓이 16인 덩어리 안에 넓이 1인 덩어리가 중첩되어 있다.
#####
#...#
#.#.#
#...#
#####
아이스크림 덩어리의 넓이와 둘레를 모두 아는 것은 중요한데, 농부 존은 궁극적으로 둘레 대 넓이의 비율, 즉 그가 얼음둘레 측도라고 부르는 값을 최소화하고 싶기 때문이다. 이 비율이 작으면 질량에 비해 표면적이 작으므로 아이스크림이 더 천천히 녹는다.
출제자: Brian Dean
출제자: Brian Dean
입력의 첫째 줄에 \(N\)이 주어지고, 다음 \(N\)개의 줄에 기계의 출력이 주어진다. '#' 문자가 적어도 하나 존재한다.
공백으로 구분된 두 정수를 한 줄에 출력한다. 첫 번째는 가장 큰 덩어리의 넓이이고, 두 번째는 그 둘레이다. 넓이가 가장 큰 덩어리가 여러 개라면, 그중 둘레가 가장 작은 것의 정보를 출력한다.
perimeter.in · 출력을 쓸 파일 perimeter.out6
##....
....#.
.#..#.
.#####
...###
....##13 22riseoj 작성
출처 올림피아드 > USACO > 2018-2019 > January > Silver