[SWEA] 2105. 디저트 카페(Python) / Brute Force

SW Expert Academy

# 1시간 32분 소요

사용 알고리즘 : Brute Force + Simulation 모든 경우의 수에 대해 다 검사해야 하는 완전탐색 문제이다.

• 마름모를 그릴 때 시작점이 되는 점은 행은 0부터 N-3까지, 열은 1부터 N-2까지의 영역 안에 들어야 한다.
• makeDistance(sr, sc) 함수에서 시작점의 위치 행, 열 좌표를 인자로 넣으면
  • 시작점에서 대각선 사각형을 이루는 왼쪽, 오른쪽의 대각선 한 변이 될 수 있는 각각의 길이를 이중 포문으로 구한다.
  • 이 때, 시작점의 반대편에 있는 꼭지점의 행 위치가 맵을 넘어가면 안 되므로,
  • 그 경우는 if sr+left+right > N-1: continue 로 걸러준다.
  • 이 조건문에 걸리지 않는다면 왼쪽, 오른쪽 길이가 맵 내 대각선 사각형을 이룰 수 있는 경우이므로 카페 종류를 검사한다.
• checkDesserts(sr, sc, left, right) 함수에서 시작점과 왼쪽, 오른쪽 길이 인자로 들어오면 돌면서 카페 종류를 검사한다.
  • 카페 종류가 될 수 있는 1~100가지에 대한 배열(cafe = [0] * 101)을 만들어놓는다. visited 방문 검사 개념.
  • 들린 카페의 갯수는 cnt로 카운트
  • 왼쪽 꼭지점 (lr, lc), 오른쪽 꼭지점 (rr, rc), 아래 꼭지점 (br, bc) 로 놓고
  • 왼쪽 길이, 오른쪽 길이만큼 마주보는 두 변에 해당하는 카페 종류를 검사하며 cafe에 담는다.
  • 이미 방문한 카페가 있다면 즉시 리턴한다.
  • 네 변에 대해 검사가 끝나면 들린 카페 갯수와 MAX값 중 최댓값을 갱신한다.

 

파이썬 코드는 다음과 같다.

---

# 시작점과 왼쪽, 오른쪽 길이 인자로 들어오면 돌면서 카페 종류 검사
def checkDesserts(sr, sc, left, right):
    global MAX
    cafe = [0] * 101	# 카페 종류 검사용
    cnt = 0             # 들린 카페 갯수
    lr = sr + left      # 왼쪽 꼭지점
    lc = sc - left
    rr = sr + right     # 오른쪽 꼭지점
    rc = sc + right
    br = sr + left + right      # 아래 꼭지점
    bc = sc + right - left

    # 왼쪽 길이만큼 두 변 검사
    for dis in range(1, left+1):
        if cafe[A[sr+dis][sc-dis]]:
            return
        cafe[A[sr+dis][sc-dis]] = 1
        if cafe[A[br-dis][bc+dis]]:
            return
        cafe[A[br-dis][bc+dis]] = 1
        cnt += 2

    # 오른쪽 길이만큼 두 변 검사
    for dis in range(1, right+1):
        if cafe[A[lr+dis][lc+dis]]:
            return
        cafe[A[lr+dis][lc+dis]] = 1
        if cafe[A[rr-dis][rc-dis]]:
            return
        cafe[A[rr-dis][rc-dis]] = 1
        cnt += 2

    # print(cafe)
    MAX = max(MAX, cnt)     # 최댓값 갱신


# 시작점 기준으로 좌, 우 가능한 거리 경우의 수 구하기
def makeDistance(sr, sc):
    for left in range(1, sc+1):
        for right in range(1, N-sc):
            if sr+left+right > N-1:     # 반대편 꼭지점이 맵 넘어가면 continue
                continue
            checkDesserts(sr, sc, left, right)

# main
T = int(input())
for tc in range(T):
    N = int(input())
    A = [list(map(int, input().split())) for _ in range(N)]
    MAX = -1
    for sr in range(N-2):
        for sc in range(1, N-1):
            makeDistance(sr, sc)

    print("#{} {}".format(tc+1, MAX))

---

• 시간 : 292ms / 메모리 : 60,556kb
• 고찰 : 그 동안 이 문제를 푼 방법들 중에 시간, 메모리를 가장 적게 소모한 코드이다. 나름대로 효율적이고 깔끔하게 짜려고 노력했던 보람이 있었다. 처음에 대각선 네 변을 그리는 것을 dfs로 풀려고 접근했었는데, 꼬여서.. 그냥 시뮬레이션 문제처럼 그림에 있는 그대로 모든 경우에 대해 다 검사를 해줬다. 푸는데 시간은 좀 걸렸지만 나름대로 재밌었다 ㅋㅋㅋ