[알고리즘] 디저트 카페

포인트

• DFS를 이용하여 정해진  규칙에 맞게 백트랙킹을 할 수 있냐? 하는 문제입니다. 
• 문제를 해석하는데 조금 어려움이 있었으나 이내 해결을 했었습니다. 저는 보통 코드를 시작할 때 입력과 출력을 먼저 맞춰 두고 생각을 하는 편인데 여러분들이 편한대로 실행을 하시면 좋을 것 같습니다. 

🧶문서는 항상 수정될 수 있습니다. 비판은 환영합니다. 

python

import sys

sys.stdin = open('input.txt')

dx = [1, 1, -1, -1]
dy = [1, -1, -1, 1]


def go(x: int, y: int, line: int, sx: int, sy: int) -> None:
    """
    사각으로 탐색을 하면서 되는 것 안되는 것을 체크하는 재귀하는 함수
    :param x:int
    :param y:int
    :param line:int
    :param sx:int
    :param sy:int
    :return:None
    """
    if not (0 <= x < n and 0 <= y < n):
        return
    # 범위가 넘어가면 백트랙킹
    if line == 3 and x == sx and y == sy:
        sel.append(len(visited))
        return
    # 방향을 3번 바꾸었고 시작점과 도착점이 같으면

    if data[x][y] in visited:
        return
    # 만약 중복 값이 있으면

    if line >= 4:
        return
    # 라인이 넘어갔으면

    # 쭉 이어서 가는 경우
    visited.add(data[x][y])
    go(x + dx[line], y + dy[line], line, sx, sy)
    visited.remove(data[x][y])

    # 방향을 꺽는 경우
    if line < 3:
        visited.add(data[x][y])
        go(x + dx[line + 1], y + dy[line + 1], line + 1, sx, sy)
        visited.remove(data[x][y])


for test in range(1, int(input()) + 1):
    n = int(input())

    data = [list(map(int, input().split())) for _ in range(n)]

    result = -987654321
    sel = []
    for row in range(n - 1):
        for col in range(1, n - 1):
            # 각 양쪽은 사각형을 그리면서 탐색을 할 수 없다.
            # 맨 끝 라인은 사각형으로 탐색을 할 수 없다.
            visited = set()
            go(row, col, 0, row, col)

    result = max(sel) if sel else -1
    print('#{} {}'.format(test, result))