[SWEA] 2105. 디저트 카페

2105. 디저트 카페

 

#디저트 한번만
#가장 많은 디저트 수
#먹을 수 없는 경우 -1
def dfs(startX, startY, x, y,idx):
    global answer
    for i in range(idx, 4):
        nx=x+dx[i]
        ny=y+dy[i]
        
        if nx==startX and ny==startY and len(dessert)>=3:
            answer=max(answer, len(dessert))
            return
          
        if nx<0 or nx>=n or ny<0 or ny>=n: continue
        if graph[nx][ny] in dessert: continue
        dessert.add(graph[nx][ny])
        dfs(startX, startY, nx,ny,i)
        dessert.remove(graph[nx][ny])
    

T=int(input())
for tc in range(1, T+1):
    n=int(input())
    graph=[list(map(int,input().split())) for _ in range(n)]
  
    
    dx=[1,1,-1,-1]
    dy=[1,-1,-1,1]
    answer=0
    
    for i in range(n-2):
        for j in range(1, n-1):
            dessert=set()
            dessert.add(graph[i][j])
            dfs(i,j,i,j,0)
  
    if answer==0:
        answer=-1
    print(f'#{tc} {answer}')