SWEA 2105 디저트 카페(with Python)

• 속도가 매우 빠른 다른 사람의 풀이를 봤는데, 만들 수 있는 사각형을 모두 구해서 중복 있는지 체크하는 방식으로 풀었다.

• DFS 보다 4배 빠르다... ㅠ (다른 사람 풀이 참고 바람...!)

dirs = [
    [-1, 1],
    [1, 1],
    [1, -1],
    [-1, -1],
]

def dfs(cr, cc, dir, score, is_rectangle):
    global answer, is_large
    if 0 <= cr < N and 0 <= cc < N:
        # 한번을 돌았지만, 같은 꼭짓점에서 만나지 못한 경우
        if is_rectangle >= 1 and dir >= 1:
            return
        # 사각형을 완성한 경우
        if score > 0 and cr == r and cc == c:
            if answer < score:
                answer = score
            return
        # 기존 사각형 보다 작을 수 밖에 없는 경우
        if dir == 3 and len(desserts.keys()) * 2 <= answer:
            return
        # 같은 숫자가 나온 경우
        if desserts.get(brd[cr][cc]):
            return

        desserts[brd[cr][cc]] = 1

        dfs(cr+dirs[dir][0], cc+dirs[dir][1], dir, score+1, is_rectangle)
        # 사각형 만들었는지 체크하기 위한 변수
        if is_rectangle == 0:
            is_rectangle = (dir+1)//4
        dfs(cr+dirs[(dir+1)%4][0], cc+dirs[(dir+1)%4][1], (dir+1)%4, score+1, is_rectangle)
        del desserts[brd[cr][cc]]

T = int(input())

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

    for r in range(N):
        for c in range(N):
            desserts = {}
            dfs(r, c, 0, 0, 0)

    print(f'#{tc} {answer}')