[SWEA][Python] 2105 디저트카페

dfs 분기를 이용해 사각형을 그리도록 직선이동 시킴. 간만큼 돌아오도록 dx, dy를 이용해 통제.

 

# 기본적으로 방향성 유지 이동, 간만큼 돌아오도록 dx, dy 변수가 늘어났다가 0으로 돌아오게끔 통제.
def dfs(x, y, dx, dy, direction, cnt):
    global max_size
    nx, ny = x + delta[direction][0], y + delta[direction][1]
    # 속행
    if 0 <= nx < N and 0 <= ny < N and not visited[nx][ny] and not check_num[matrix[nx][ny]]:
        visited[nx][ny] = True
        check_num[matrix[nx][ny]] = True
        if direction == 0:
            dfs(nx, ny, dx + 1, dy, direction, cnt + 1)
            dfs(nx, ny, dx + 1, dy, direction + 1, cnt + 1)
        elif direction == 1:
            dfs(nx, ny, dx, dy + 1, direction, cnt + 1)
            dfs(nx, ny, dx, dy + 1, direction + 1, cnt + 1)
        elif direction == 2:
            if dx > 1:
                dfs(nx, ny, dx - 1, dy, direction, cnt + 1)
            else:
                dfs(nx, ny, dx - 1, dy, direction + 1, cnt + 1)
        else:
            dfs(nx, ny, dx, dy - 1, direction, cnt + 1)
        visited[nx][ny] = False
        check_num[matrix[nx][ny]] = False
    if nx == i and ny == j:
        max_size = max(max_size, cnt)


for test in range(1, int(input()) + 1):
    N = int(input())
    matrix = [list(map(int, input().split())) for _ in range(N)]
    check_num = {i: False for i in range(1, 101)}
    visited = [[False] * N for _ in range(N)]
    delta = ((1, -1), (1, 1), (-1, 1), (-1, -1))
    max_size = -1
    # start
    for i in range(N - 1):
        for j in range(1, N - 1):
            check_num[matrix[i][j]] = True
            visited[i][j] = True
            dfs(i, j, 0, 0, 0, 1)
            check_num[matrix[i][j]] = False
            visited[i][j] = False
    print(f'#{test} {max_size}')