[백준(Baekjoon)] 1051 숫자 정사각형

문제

N*M크기의 직사각형이 있다. 각 칸은 한 자리 숫자가 적혀 있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행 또는 열에 평행해야 한다.

 

입력

첫째 줄에 N과 M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 수가 주어진다.

 

출력

첫째 줄에 정답 정사각형의 크기를 출력한다.

 

입력	출력
3 5 42101 22100 22101	9

 

---

나의 풀이

[Python(파이썬)]

a, b = map(int, input().split())
c = [input() for _ in range(a)]
answer = 1
for i in range(a-1):
    for j in range(b-1):
        for k in range(min(j+a-1, b-1), j, -1): #
            if c[i][j] == c[i][k]:
                temp = k - j
                if i + temp < a and c[i][j] == c[i+temp][j] == c[i+temp][j+temp]:
                    if answer < (temp + 1) * (temp + 1):
                        answer = (temp+1) * (temp+1)
                    break
print(answer)

---

 

풀이 과정

1. for문
2. j, k 비교
3. 정사각형 확인

 

1. for문

for i in range(a-1):
    for j in range(b-1):
        for k in range(min(j+a-1, b-1), j, -1):

 

아래 그림은 for문의 변수들이 움직이는 방향을 나타낸다. 

정사각형 꼭짓점을 찾기 위해서 우선 같은 줄에서 같은 수를 찾는다. -> i가 세로인 이유

j 방향과 k 방향이 반대인 이유는 뒤에서 설명하도록 하자

 

 

2. j, k 비교

 

 for j in range(b-1):
        for k in range(min(j+a-1, b-1), j, -1): #
            if c[i][j] == c[i][k]:
                temp = k - j

 

우선 같은 줄에서 같은 수를 찾기 위해 i를 고정해두고 j와 k를 비교한다. -> if c[i][j] == c[i][k]

j는 0번 인덱스부터 오른쪽으로 움직이고 k는  min(j+a-1, b-1)부터 j+1까지 왼쪽으로 움직인다. 

 

 

• j와 k방향이 반대인 이유

j를 고정해두고 k가 k += 1되면서 오른쪽으로 이동한다면 정사각형을 발견하더라도 다음 k에서 더 큰 정사각형이 있으므로 계속 확인해야한다. 하지만 k -= 1을 하며 왼쪽으로 이동한다면 그것이 j와 k가 만들 수 있는 가장 큰 정사각형이므로 k를 break할 수 있다.  

 

 

 

 

 

※ k가 min(j+a-1, b-1)부터 j+1까지 움직이는 이유

 

세로의 길이가 가로의 길이보다 길 때는 k의 range가 (b-1, j, -1)면 상관없겠지만 세로의 길이가 가로의 길이보다 짧을 때는 그림 min(j+a-1, b-1) 이유 1 처럼 j에서 세로의 길이만큼을 제외한 뒤의 인덱스들은 정사각형이 될 수 없기 때문에 확인 할 필요가 없다. 

따라서 k의 range가  j+a-1부터 시작되어야만 한다. 

그림 min(j+a-1, b-1) 이유 1

 

 

그리고 b(가로 길이) - j가 세로의 길이보다 작게 남았을 때는 세로의 길이만큼 구하는 (j+a-1)는 IndexError를 초래한다. 

 그림 min(j+a-1, b-1) 이유 2 처럼 j가 3일때 (j+a-1)는 5가 된다. 따라서 k의 range가  b-1부터 시작되어야만 한다. 

 

그림 min(j+a-1, b-1) 이유 2

 

 

위의 두가지 경우를 다 해결하기 위해 min(j+a-1, b-1)부터 시작하는 것이다. 

 

 

3.  정사각형 확인

 

if i + temp < a and c[i][j] == c[i+temp][j] == c[i+temp][j+temp]:
    if answer < (temp + 1) * (temp + 1):
        answer = (temp+1) * (temp+1)
    break

 

1) i + temp < a  -> 뒤에 c[i+temp][j] 할 때 인덱스 에러가 나지 않기 위해 미리 확인

2) c[i][j] == c[i][k] (위의 두개 꼭짓점)가 같은지 확인한 다음 아래 두개의 꼭짓점도 위의 꼭짓점과 같은지 확인

     c[i][j] == c[i+temp][j] == c[i+temp][j+temp]

3) answer < (temp + 1) * (temp + 1) -> 현재 정사각형이 가장 큰 정사각형인지 확인

 

---

문제 출처

1051번: 숫자 정사각형