[백준 / 1051] 숫자 정사각형 - Python

https://www.acmicpc.net/problem/1051

1051번: 숫자 정사각형

<접근>

원하는 정사각형의 조건은 같은 행, 같은 열에 존재한다. 한 노드를 기준으로 같은 줄의 같은 숫자를 찾아서 해당 거리를 구하고, 그 거리만큼 떨어진 사각형의 위치에 같은 숫자가 존재하는지를 판단하면 된다.

<입력>

N, M = map(int, input().split())

square = []
for _ in range(N):
    square.append(list(map(int, input())))

 

N행 M열을 입력받는다.

사각형을 입력받아 square에 저장한다.

<같은 수 찾기>

foursquare = 1

for row in range(N-1):
    for col in range(M-1):
        num = square[row][col]

        for next_col in range(col+1, M):
            if num == square[row][next_col]:
                gap = next_col-col

 

가장 큰 정사각형의 한 변의 크기를 담을 변수 foursquare를 선언한다. 1로 초기화한 이유는 아래의 코드는 원하는 두 지점을 찾는 것인데, 두 지점이 존재하지 않는 경우 1개가 가장 큰 정사각형이므로 1로 초기화한다.

 

N-1과 M-1만큼 탐색하는 이유는 아래의 코드는 두 지점을 찾는 것이므로 오른쪽과 아래쪽 하나씩 남겨둔다.

한 수를 기준으로 num에 저장하여 비교해준다. 같은 줄에 있는 다음 수부터 비교하여 같은 수가 나오면 해당 수와 기준 수와의 차이를 gap에 저장해둔다.

<비교하기>

                if row+gap < N:
                    if num == square[row+gap][col] and num == square[row+gap][next_col]:
                        if gap+1 > foursquare:
                            foursquare = gap+1

print(foursquare**2)

 

길이 gap과 row를 더했을 때 범위를 넘어가면 에러가 나므로 더 작은 경우만 비교해준다.

나머지 두 점을 비교하여 nu과 같으면 해당 지점은 정사각형이므로 gap과 foursquare를 비교하여 gap이 더 크다면 갱신해준다. 해당 점도 길이에 포함되므로 1을 더해준다.

<전체 코드>

N, M = map(int, input().split())

square = []
for _ in range(N):
    square.append(list(map(int, input())))

foursquare = 1

for row in range(N-1):
    for col in range(M-1):
        num = square[row][col]

        for next_col in range(col+1, M):
            if num == square[row][next_col]:
                gap = next_col-col

                if row+gap < N:
                    if num == square[row+gap][col] and num == square[row+gap][next_col]:
                        if gap+1 > foursquare:
                            foursquare = gap+1

print(foursquare**2)