[백준 / Python 파이썬] 22994번 - 이미지 축소

[Silver II] 이미지 축소 - 22994

---

문제 링크

분류

브루트포스 알고리즘, 유클리드 호제법, 구현, 수학, 정수론

문제 설명

세로 n 픽셀, 가로 m 픽셀로 구성된 직사각형 형태의 이미지가 있다. 정휘는 적당한 자연수 i,j를 선택해서 이미지의 세로 길이를 i배, 가로 길이를 j배 확대해서 세로 ni 픽셀, 가로 mj 픽셀 이미지를 만들었다. 하지만 모종의 이유로 원본 이미지가 삭제되어 여러분들에게 원본 이미지 복원을 요청했다.

확대된 이미지가 주어지면 가능한 원본 이미지 중 가장 작은 원본 이미지를 구해서 출력하라. 이때, 구현의 편의를 위해 각 픽셀의 정보는 알파벳 소문자 (a, b, ... , z; 아스키 코드 97-122) 로 표현한다.

입력

첫째 줄에 확대된 이미지의 크기를 나타내는 정수 ni,mj가 공백으로 구분되어 주어진다.

둘째 줄부터 ni줄에 걸쳐, 각 줄마다 이미지의 각 픽셀 값을 나타내는 mj개의 알파벳이 주어진다.

출력

가능한 원본 이미지 중 넓이가 가장 작은 것을 출력한다.

첫째 줄에 원본 이미지의 세로 길이와 가로 길이를 의미하는 정수 n,m을 공백으로 구분해서 출력한다.

둘째 줄부터 n줄에 걸쳐, 각 줄마다 원본 이미지를 나타내는 m개의 알파벳을 출력한다.

가능한 답안이 여러 가지 있으면 아무거나 출력해도 된다.

---

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
images = [list(input().strip()) for _ in range(N)]

w = 1001
for i in range(N):
    c = images[i][0]
    r = 1
    for j in range(1, M):
        if c == images[i][j]:
            r += 1
        else:
            w = min(w, r)
            c = images[i][j]
            r = 1

if w == 1001:
    w = M

if M % w != 0:
    w = 1

h = 1001
for i in range(M):
    c = images[0][i]
    r = 1
    for j in range(1, N):
        if c == images[j][i]:
            r += 1
        else:
            h = min(h, r)
            c = images[j][i]
            r = 1

if h == 1001:
    h = N

if N % h != 0:
    h = 1

print(N//h, M//w)
for i in range(0, N, h):
    for j in range(0, M, w):
        print(images[i][j], end="")
    print()