[Python] SW Expert Academy #2105 디저트 카페

📚문제: #2105 디저트 카페(모의 SW 역량테스트)

전체 코드

# 2105. 디저트 카페

# 먹을 수 있는 디저트 계산
def MAX_DESSERT(t, n, G):
    
    # 디저트 수량
    max_cnt = -1
    
    # 대각선 방향, 순서대로 (우하, 좌하, 좌상, 우상)
    dr = [1, 1, -1, -1]
    dc = [1, -1, -1, 1]
    
    # 최종 돌아온 좌표가 시작지점이면 직사각형이 성립한다.
    
    # 모든 좌표에서 시작해본다.
    for r in range(n):
        
        for c in range(n):
            
            for i in range(1, n-1):
                
                for j in range(1, n-1):
                    
                    for p in range(1, n-1):
                        
                        for q in range(1, n-1):
                            
                            is_rectangle = True
                            
                            # 직사각형이 아닌 모양일 때, 마주보는 두 변의 길이는 같아야 함
                            if i != p or j != q:
                                
                                continue
                            
                            # 각 방향으로 움직이는 거리
                            moving = [i, j, p, q]
                            
                            # 시작 좌표
                            s_r = r
                            s_c = c
                            
                            # 현재 좌표
                            cur_r = r
                            cur_c = c
                            
                            # 직사각형 좌표 값
                            val = [G[s_r][s_c]]
                            
                            for x in range(4):
                                
                                for _ in range(moving[x]):
                                    
                                    # 좌표 갱신
                                    cur_r, cur_c = cur_r + dr[x], cur_c + dc[x]

                                    # 주어진 범위를 벗어나지 않을 때
                                    if 0 <= cur_r <= n-1 and 0 <= cur_c <= n-1:
                                        
                                        val.append(G[cur_r][cur_c])
                                        
                                    else:
                                        
                                        # 직사각형을 만족하지 않을 때 Skip
                                        is_rectangle = False
                                        break
                                
                                if not is_rectangle:
                                    
                                    break
                            
                            if not is_rectangle:
                                
                                continue
                            
                            else:
                                
                                val = list(set(val))
                                
                                # 중복되는 카페가 없을 때 갱신
                                if len(val) == i+j+p+q:
                                    
                                    max_cnt = max(max_cnt, len(val))
                                
                                else:
                                    
                                    continue
                                         
    # 답안 출력
    print("#{} {}".format(t, max_cnt))
    
# 테스트 케이스 T가 주어진다.
T = int(input())

# T개의 테스트 케이스
for t in range(1, T+1):
    
    # 한 변의 길이 N
    N = int(input())
    
    # 디저트 카페
    cafe = []
    
    # N줄에 걸쳐 N × N 크기의 디저트 종류가 주어진다.
    for _ in range(N):
        
        cafe.append(list(map(int, input().split())))
    
    # 함수 실행
    MAX_DESSERT(t, N, cafe)

TIL

N × N Grid에서 직사각형을 형성할 수 있는 모든 케이스를 찾아본다. 직사각형 한 변의 최대 길이는 N-2이다. 또한 마주보는 변의 길이가 서로 같을 때만 직사각형 형성이 가능하다. 마주보는 변의 길이가 다를 때는 Skip하여 시간을 단축한다. 좌표탐색을 실행하다가 Grid의 범위를 벗어날 때도 Skip한다. 마지막으로 중복되는 카페가 있는지 살펴본다.