문제

디저트 카페 문제 링크

아이디어

✅ 시계 방향이나 반시계 방향 중 하나를 선택하여 회전을 해야한다. 또한, 각 모서리에서는 시작할 수 없고, 맨 두 줄에서는 시작할 수 없다는 것을 생각했지만 구현이 어려워서 생각하고 시도했지만 결국 클론했다

[#Error] 내 코드_python

from collections import deque

T = int(input())
x = [1, 1, -1, -1]
y = [-1, 1, 1, -1]

for t in range(1, T + 1):
    n = int(input())
    cafe = [list(map(int, input().split())) for _ in range(n)]
    queue = deque() #[i, j] 위치 표시
    arr = deque()    #들어간 숫자 표시

    for i in range(len(cafe)-2):
        for j in range(1, len(cafe[i])-1):
            visited = [[False] * n for x in range(n)]
            arr.append(cafe[i][j])
            queue.append([i,j])
            visited[i][j] = True
            for k in range(4):
                i += x[k]
                j += y[k]
                while i < n and j < n:
                    if visited[i][j] == False and cafe[i][j] not in arr:
                        arr.append(cafe[i][j])
                        queue.append([i,j])
                        visited[i][j] = True
                        i += x[k]
                        j += y[k]
                    else:
                        arr.pop()
                        queue.pop()
                        if len(arr) == 1:
                            answer = -1
                            break
                        i = queue[-1][0] + x[k-1]
                        j = queue[-1][1] + y[k-1]
        print(arr)

[#Clone] 정답 코드_python

✅ 카페와 디저트 종류를 방문했는지 표시하는 배열을 만든다.
dfs를 이용하여 회전 방향을 정하고 반복하여 최대값을 출력한다.

directions = [(1, -1), (1, 1), (-1, 1), (-1, -1)]

def dfs(i, j, dir, cnt):
    global answer

    if dir < 3:
        tmp = dir + 2
    else:
        tmp = dir + 1
    for k in range(dir, tmp):
        ni = i + directions[k][0]
        nj = j + directions[k][1]
        if start[0] == ni and start[1] == nj:
            answer = max(answer, cnt)
            return
        if 0 <= ni < n and 0 <= nj < n:
            if cafe_visited[ni][nj] == False and dessert_visited[arr[ni][nj]] == False:
                cafe_visited[ni][nj] = True
                dessert_visited[arr[ni][nj]] = True

                dfs(ni, nj, k, cnt + 1)

                cafe_visited[ni][nj] = False
                dessert_visited[arr[ni][nj]] = False

T = int(input())
for t in range(1, T+1):
    n = int(input())
    arr = [list(map(int, input().split())) for x in range(n)]

    cafe_visited = [[False]*n for x in range(n)]
    dessert_visited = [False] * 101
    answer = -1

    for i in range(n-2):
        for j in range(1, n-1):
            start = (i, j)
            cafe_visited[i][j] = True
            dessert_visited[arr[i][j]] = True

            dfs(i, j, 0, 1)
            cafe_visited[i][j] = False
            dessert_visited[arr[i][j]] = False
    print(f'#{t} {answer}')

clone함수 출처 링크