(22 복습) 2105. [모의 SW 역량테스트] 디저트 카페 : 게리맨더링 2 규칙 활용

[sallyy1]

• 게리맨더링 규칙(백준 게리맨더링 문제) 활용해 대각선 테두리 탐색하는 코드 구현해봄
• 4가지 방향에서의
• (행, 열)의 범위 따지고,
• 행 -/+ 여부, 열 -/+ 여부 규칙 따지기
• 브루트 포스로 d1과 d2의 범위 for문 돌려서 + 격자를 벗어나는 d1 및 d2는 제외하고 나머지에 대해 대각선 사각형 만들어나가면 됨

    for x in range(N):
        for y in range(N):
            ## <시작점 (x, y) 기준으로> 문제 조건을 만족하는 디저트 카페 루트 탐색 !!


            # 게리맨더링 -> 브루트포스로 수행
            for d1 in range(1, N):
                for d2 in range(1, N):
                    ## (격자 밖을 벗어나는 경우 -> 불가능)
                    if (x + d1 + d2) > (N-1): continue
                    if (y + d2) > (N-1): continue
                    if (y - d1) < 0: continue

                    check = [[0]*N for _ in range(N)]
                    i, j = x, y
                    check[i][j] = 1
                    #print((i, j))

                    temp = []
                    temp.append(a[i][j])


                    # 4가지 방향(시계 방향) 순차적으로 진행 - 대각선 테두리
                    while x <= i < (x + d2) and y <= j < (y + d2):
                        i += 1
                        j += 1
                        check[i][j] = 1
                        #print((i, j))

                        temp.append(a[i][j])




                    while (x + d2) <= i < (x + d1 + d2) and (y + d2) >= j > (y - (d1-d2)):
                        i += 1
                        j -= 1
                        check[i][j] = 1
                        #print((i, j))

                        temp.append(a[i][j])




                    while (x + d1 + d2) >= i > (x + d1) and (y - (d1-d2)) >= j > (y - d1):
                        i -= 1
                        j -= 1
                        check[i][j] = 1
                        #print((i, j))

                        temp.append(a[i][j])




                    while (x + d1) >= i > x and (y - d1) <= j < y:
                        i -= 1
                        j += 1
                        check[i][j] = 1
                        #print((i, j))

                        temp.append(a[i][j])

풀이

## 게리맨더링과 같은 규칙 수행 !! (대각선 마름모 경계선 구하기)


T = int(input())

for test_case in range(1, T+1):
    N = int(input())
    a = [list(map(int, input().split())) for _ in range(N)]

    answer = -1
    all_cases = []


    for x in range(N):
        for y in range(N):
            ## <시작점 (x, y) 기준으로> 문제 조건을 만족하는 디저트 카페 루트 탐색 !!


            # 게리맨더링 -> 브루트포스로 수행
            for d1 in range(1, N):
                for d2 in range(1, N):
                    ## (격자 밖을 벗어나는 경우 -> 불가능)
                    if (x + d1 + d2) > (N-1): continue
                    if (y + d2) > (N-1): continue
                    if (y - d1) < 0: continue

                    check = [[0]*N for _ in range(N)]
                    i, j = x, y
                    check[i][j] = 1
                    #print((i, j))

                    temp = []
                    temp.append(a[i][j])


                    # 4가지 방향(시계 방향) 순차적으로 진행 - 대각선 테두리
                    while x <= i < (x + d2) and y <= j < (y + d2):
                        i += 1
                        j += 1
                        check[i][j] = 1
                        #print((i, j))

                        temp.append(a[i][j])




                    while (x + d2) <= i < (x + d1 + d2) and (y + d2) >= j > (y - (d1-d2)):
                        i += 1
                        j -= 1
                        check[i][j] = 1
                        #print((i, j))

                        temp.append(a[i][j])




                    while (x + d1 + d2) >= i > (x + d1) and (y - (d1-d2)) >= j > (y - d1):
                        i -= 1
                        j -= 1
                        check[i][j] = 1
                        #print((i, j))

                        temp.append(a[i][j])




                    while (x + d1) >= i > x and (y - d1) <= j < y:
                        i -= 1
                        j += 1
                        check[i][j] = 1
                        #print((i, j))

                        temp.append(a[i][j])





                    ### (첫 시도 - 이렇게 풀면 직사각형에서느 안 맞음)
                    '''
                    for i in range(x, (x + d2)):
                        for j in range(y, (y + d2)):
                            check[i][j] = 1
                            print((i, j))

                    for i in range((x + d2), (x + d1 + d2)):
                        for j in range((y + d2), (y - (d1-d2)), -1):
                            check[i][j] = 1
                            print((i, j))

                    for i in range((x + d1 + d2), (x + d1), -1):
                        for j in range((y - (d1-d2)), (y - d1), -1):
                            check[i][j] = 1
                            print((i, j))

                    for i in range((x + d1), x, -1):
                        for j in range((y - d1), y):
                            check[i][j] = 1
                            print((i, j))
                    '''

                    # print('### 시작점 : ', (x, y), d1, d2)
                    # for line in check:
                    #     print(line)

                    ## 문제 조건을 만족하는 디저트 카페 루트 저장 !!
                    ## (주의) 마지막 4번째 방향에서는 -> 시작점은 제외시켜줘야 함
                    #####print(temp[:-1])
                    if len(temp[:-1]) == len(set(temp[:-1])):
                        all_cases.append(len(temp[:-1]))





    if len(all_cases) != 0:
        answer = max(all_cases)

    print('#{0} {1}'.format(test_case, answer))