BOJ 15636 Linear Algebra and Group

문제 링크
아래 표지에 있는 숫자들의 합을 계산하는 문제이다.

"선형대수와 군"(이인석, 개정판)

그림을 인터넷에서 다운 받은 후, 어떤 특징이 있는지 관찰해보자.
같은 숫자가 적힌 칸의 배경색이 모두 동일하다는 사실을 알 수 있다. 예를 들어, 1이 적혀있는 칸은 분홍색으로 색칠되어 있고 0이 적혀있는 칸은 빨간색으로 색칠되어 있다.
그림은 29개의 줄과 50개의 열로 구성되어 있으며, 총 1450개의 숫자칸이 존재한다. 각 칸에 대한 RGB 값으로 clustering하면 되겠다는 전략을 세웠다. 숫자 부분은 각 칸에서 차지하는 영역이 크지 않으므로 무시하고, 모든 칸의 테두리에 있는 검은 경계선을 제외시킨다. 각 칸에 존재하는 모든 픽셀들에 대한 RGB값의 평균을 다음과 같이 계산할 수 있다.

clustering이 성공적으로 잘 이루어졌음을 확인할 수 있다. 이제 각 cluster에 속하는 원소의 개수와 원본 이미지가 무엇인지를 알면, 문제에서 요구하는 숫자들의 합을 계산할 수 있다. 

어떤 숫자가 몇 개인지 알았으니, 단순히 다 더해서 그 값을 제출하면 문제를 맞출 수 있다.

Github repository에서 코드와 이미지를 확인할 수 있다.