행렬과 행렬과 배열과 행렬과 배렬과 행열과......

자주 만나는 행렬 문제들을 풀어본다.

 

쉬운 문제는 어떻게 풀긴 하겠다. 하지만 인덱스를 고려하고, 2차원 행렬을 탐색하고 여행하는 과정은 무척이나 머리가 아팠다.

 

오늘의 실패 문제를 알아보자.

 

숫자 정사각형 - https://www.acmicpc.net/problem/1051

각 꼭지점의 숫자를 찾아낼 인덱스를 어떻게 정의하고 찾아내는지가 풀이의 방법이었다.

 

결과 풀이 : 

48ms

# 방식은 알았으나 구현이 힘들었음. 자료 참고하여 품

n, m = map(int, input().split())
max_length = min(n, m)  # 정사각형 한변의 최대 길이
numbers = [input().strip() for _ in range(n)]

# for문 3개를 이용함. -> 처음엔 2개로만 쓰려고 했는데 모든 범위를 체크하지 못함

def square(numbers, n, m):
    max_size = 0
    # 정사각형의 사이즈는 주어진 n m중 작은 값까지 커질 수 있음 ( max_length = min(n,m))
    # 각 정사각형의 사이즈별로 4 꼭지점의 값을 분석함

    for size in range(1, max_length + 1):  # size = 1, 2, 3
        # 인덱스로 사용할 i , j의 값을 잘 정해야 범위를 넘지 않는다.
        # 인덱스의 범위는 입력값의 크기와 관련되어 정해진다.
        # 인덱스의 증가 값은 정사각형 변의 길이 (size) - 1이다.
        # i, j가 증가하는 값은 (전체 숫자 길이) - size + 1 까지 증가한다.
        for i in range(n - size + 1):
            for j in range(m - size + 1):
                if numbers[i][j] == numbers[i][j + size - 1] == numbers[i + size - 1][j] == numbers[i + size - 1][
                    j + size - 1]:
                    max_size = max(max_size, size) # 네개의 수가 모두 같다면 정사각형 크기를 갱신하여 저장한다.
    return max_size

# 넓이는 제곱으로 표현
print(square(numbers, n, m) ** 2)

 

N X M 크기의 직사각형 -> 입력값은 N, M개의 숫자로 이루어져있다.

 

이 숫자 배열에서 꼭짓점에 쓰여있는 수가 모두 같은, 가장 큰 정사각형을 찾아야 한다.

 

입력받는 과정은 제외한다. 어쨌든 저 값을 입력 받았다.

 

정사각형의 꼭짓점에 쓰여있는 숫자를 찾으려면, 각 수가 갖고있는 인덱스를 사용해야 하겠다.

[ "42101", "22100", "22101" ] 의 형태로 입력받았기때문에,  2차원 인덱스 [i][j]를 잘 꾸며보면 구할 수 있을 것이었다.

 

정사각형 한 변의 길이 : size는 입력받은 N, M중 작은 값까지 증가할 수 있다. 즉, size = 3이 최대 크기의 정사각형이다. 

 

그렇다면 size가 1, 2, 3인 경우를 다 따져보고 네 꼭지점의 값이 같으면 그 정사각형을 우선 저장한다. 

 

더 큰 정사각형이 등장하면 큰 값을 답으로 사용한다. (정사각형의 넓이)

---

 

여기까진 어떻게 잘 접근하였으나, 구현 방법에서 문제가 있었다.

 

우선 사각형의 크기에 따른 숫자들의 인덱스를 정하는 것과,

그 인덱스들의 범위 문제였다.

 

결과적으로

def square(numbers, n, m):
    max_size = 0
    # 정사각형의 사이즈는 주어진 n m중 작은 값까지 커질 수 있음 ( max_length = min(n,m))
    # 각 정사각형의 사이즈별로 4 꼭지점의 값을 분석함

    for size in range(1, max_length + 1):  # size = 1, 2, 3
        # 인덱스로 사용할 i , j의 값을 잘 정해야 범위를 넘지 않는다.
        # 인덱스의 범위는 입력값의 크기와 관련되어 정해진다.
        # 인덱스의 증가 값은 정사각형 변의 길이 (size) - 1이다.
        # i, j가 증가하는 값은 (전체 숫자 길이) - size + 1 까지 증가한다.
        for i in range(n - size + 1):
            for j in range(m - size + 1):
                if numbers[i][j] == numbers[i][j + size - 1] == numbers[i + size - 1][j] == numbers[i + size - 1][
                    j + size - 1]:
                    max_size = max(max_size, size) # 네개의 수가 모두 같다면 정사각형 크기를 갱신하여 저장한다.
    return max_size

 

이러한 함수를 사용했다.

 

차근차근 따져보면 입력값 N,M과 정사각형과 인덱스의 범위 관계를 찾아낼 수 있을 것이었다...

어쩐지 머리가 안돌아갔다. 4개 꼭짓점을 지정하는 방법도 접근은 맞았으니, 앞으로 비슷한 문제가 등장하면 다시 열심히 풀어봐야겠다.

 

코드 내에 설명을 해놨으므로.. 기록용으로 적습니다.