[SWEA][D4][#02105] 디저트 카페

출처

• SW Expert Academy

학습용 포스트입니다. 본 포스트가 문제가 될 시 수정 또는 삭제하겠습니다.

문제

문제 생략

My Sol

def turnMain(ni, nj, nd, arr):
    # 진행방향대로 가기
    turnOrGo(ni, nj, nd, arr, 0)

    # 방향 전환
    if nd < 3:
        turnOrGo(ni, nj, nd, arr, 1)


def turnOrGo(ni, nj, nd, arr, t):
    di, dj = dd[nd+t]
    si, sj = ni+di, nj+dj
    if 0<=si<N and 0<=sj<N:
        if not mat[si][sj] in arr:
            turnMain(si, sj, nd+t, arr+[mat[si][sj]])
        elif si==bi and sj==bj:
            global maxV
            maxV = max(maxV, len(arr))


dd = [(1,-1), (1,1), (-1,1), (-1,-1)]
T = int(input())
for tc in range(1, T+1):
    N = int(input())
    mat = [list(map(int, input().split())) for _ in range(N)]

    maxV = 0
    for i in range(N-2):
        lim = int((maxV>>2) * 1.5)
        if i+lim > N: break
        for j in range(1, N-1):
            bi, bj = i, j
            turnMain(i, j, 0, [mat[i][j]])

    maxV = maxV if maxV else -1
    print(f'#{tc} {maxV}')

2차원 배열의 모든 칸에 대해서 8시 방향, 4시 방향, 1시 방향, 11시 방향 순으로 돌려 사각형을 만들면 된다. 이때 한번 이동하면 계속 해당 방향으로 이동할 것인지, 아니면 방향을 꺾을 것인지를 결정하는데, 이 역시 2가지 상황 모두 고려해서 트리를 내려준다. 디저트의 중복을 확인하는 2가지 방법이 있는데,

1. 모든 트리가 방향을 4번 다 바꾸면 도착점이 시작점인지 체크하고 arr 안의 원소가 중복되는지 확인하는 로직
2. 다음으로 이동하기 전에 다음 칸의 값이 arr에 있는지 확인하는 로직

나는 2번을 선택했다. 왜냐하면 in arr 방식이 상당히 시간이 걸리는 방법이기는 하지만, 모든 트리가 리프노드가 간다고 생각한다면 너무 많은 arr를 확인해야하기 때문에 arr에 추가하기 전에 그때그때 트리의 진행을 컷해서 백트래킹하는 것이다. 즉, 다음 이동 좌표의 값이 arr에 이미 있다면, 그 방향으로는 더 나아가지 않는 방식이다. 그 이후에 어떻게 개진이 되든 불가능한 답이기 때문이다. arr에 있는지 확인하기 이전에 좌표 인덱스로 쓸 si, sj가 범위에 있는지를 체크해야 인덱스에러를 방지할 수 있다.

진행 중에 처음 점을 다시 밟게 되면 반드시 arr에 있는 값을 조회하게 된다. 이 경우를 생각해 arr에 있는지 체크하는 if 문 뒤에, elif 문으로 처음 시작점의 좌표인 bi, bj가 현재 탐색 좌표인 si, sj와 같은지 체크했고, 만약 맞다면 arr는 모두 중복되지 않는 배열이므로 그대로 길이를 계산해 maxV와 비교해 더 큰 값을 갱신하면 되겠다.

그리고 i를 진행할 때마다 maxV가 갱신이 될텐데 특정 i부터는 가장 크게 돌더라도 maxV보다 크게 나올 수 없는 지점이 생긴다. 이 이후에도 계속 로직을 돌리는 것은 비효율적이므로, 마름모의 높이와 변의 길이를 계산하여 lim 변수에 저장하고 특정 i와 lim을 더한 값이 N보다 크다면 이후의 조회는 진행하지 않고 for문을 탈출하는 방식을 사용하였다.

결과

PASS