컴퓨터에서 사진이나 그림과 같은 화상자료를 처리하기 위해서는 그 이미지를 픽셀이라는 작은 크기로 세밀하게 분할하고, 각 피셀마다 밝기와 색상 등의 정보에 따라 적절한 값을 부여하여야 한다. 이렇게 하여 만들어진 자료를 이미지 데이터라고 한다.
예를 들어 다음 그림은 각 픽셀의 밝기를 기준으로 0~9의 값을 부여한 이미지 데이터이다.
|
2 |
2 |
0 |
1 |
1 |
0 |
0 |
2 |
2 |
1 |
1 |
1 |
|
2 |
9 |
0 |
2 |
1 |
0 |
1 |
0 |
2 |
1 |
1 |
1 |
|
0 |
0 |
0 |
0 |
8 |
8 |
8 |
8 |
0 |
1 |
1 |
2 |
|
1 |
1 |
0 |
1 |
9 |
8 |
9 |
8 |
1 |
1 |
6 |
1 |
|
1 |
1 |
0 |
2 |
9 |
8 |
7 |
8 |
1 |
1 |
6 |
1 |
|
2 |
3 |
0 |
1 |
9 |
9 |
7 |
9 |
2 |
2 |
1 |
1 |
|
1 |
1 |
8 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
|
1 |
1 |
2 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
이와 같이 원본 이미지 데이터가 주어질 때, 잡티를 제거하고, 부분적으로 같은 이미지가 존재하는가를 알아보려고 한다.
먼저, 잡티를 제거하는 방법은 다음과 같다.
한 픽셀을 중심으로 이웃하는 8방향(상하좌우, 네 대각선 방향)의 픽셀을 조사한다. (단, 가장자리에 위치한 픽셀의 경우 실제 이웃하는 픽셀만 조사한다.) 중심 픽셀의 값이 주위 모든 픽셀의 값과 4 이상 차이가 나면 중심 픽셀은 잡티로 처리한다. 잡티로 판명된 픽셀은 주위 모든 픽셀 값의 평균을 반올림한 값을 새롭게 부여받는다. 위의 예에서는 2개의 잡티가 있는데 이를 제거하면 다음과 같다.
|
2 |
2 |
0 |
1 |
1 |
0 |
0 |
2 |
2 |
1 |
1 |
1 |
|
2 |
1 |
0 |
2 |
1 |
0 |
1 |
0 |
2 |
1 |
1 |
1 |
|
0 |
0 |
0 |
0 |
8 |
8 |
8 |
8 |
0 |
1 |
1 |
2 |
|
1 |
1 |
0 |
1 |
9 |
8 |
9 |
8 |
1 |
1 |
6 |
1 |
|
1 |
1 |
0 |
2 |
9 |
8 |
7 |
8 |
1 |
1 |
6 |
1 |
|
2 |
3 |
0 |
1 |
9 |
9 |
7 |
9 |
2 |
2 |
1 |
1 |
|
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
|
1 |
1 |
2 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
계속해서 잡티가 이미지 데이터에서 부분적으로 같은 이미지가 있는지를 검색한다.
검색할 부분 이미지의 크기는 3×3이다. 서로 다른 3×3 픽셀의 값이 일치하거나 또는 회전하여 일치하는 경우 (90도, 180도, 270도 회전) 그 두 곳의 이미지는 같다라고 한다. 아래 예에서는 굵은 선으로 표시된 두 곳의 픽셀 값이 180도 회전하면 일치하므로 두 곳의 이미지가 서로 같다고 할 수 있다.
원본 이미지 데이터가 주어질 때, 잡티를 제거하고, 부분적으로 같은 이미지를 찾아내는 프로그램을 작성하시오.
입력
출력
아래의 예와 같이, 같은 이미지가 있는 모든 곳을 #으로 표시한다.
입출력 예
입력
8 12
2 2 0 1 1 0 0 2 2 1 1 1
2 9 0 2 1 0 1 0 2 1 1 1
0 0 0 0 8 8 8 8 0 1 1 2
1 1 0 1 9 8 9 8 1 1 6 1
1 1 0 2 9 8 7 8 1 1 6 1
2 3 0 1 9 9 7 9 2 2 1 1
1 1 8 0 1 0 0 0 1 1 1 1
1 1 2 0 1 0 0 0 1 1 1 1
출력
2 2 0 1 1 0 0 2 2 1 1 1
2 1 0 2 1 0 1 0 2 1 1 1
0 0 0 0 8 8 8 8 0 1 1 2
1 1 0 1 9 8 9 8 1 1 6 1
1 1 0 2 9 8 7 8 1 1 6 1
2 3 0 1 9 9 7 9 2 2 1 1
1 1 1 0 1 0 0 0 1 1 1 1
1 1 2 0 1 0 0 0 1 1 1 1
2 2 0 1 1 0 0 2 2 # # #
2 1 0 2 1 0 1 0 2 # # #
0 0 0 0 8 8 8 8 0 # # #
1 1 0 1 9 8 9 8 1 1 6 1
1 1 0 2 9 8 7 8 1 1 6 1
2 3 0 1 9 9 7 9 2 # # #
1 1 1 0 1 0 0 0 1 # # #
1 1 2 0 1 0 0 0 1 # # #
출처 : KOI 지역본선 기출문제 문제 작업+데이터:tncks0121(박수찬)