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

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5VwAr6APYDFAWu 

SW Expert Academy

< 📝 문제 >
친구들과 디저트 카페 투어를 할 계획이다.

[Fig. 1]과 같이 한 변의 길이가 N인 정사각형 모양을 가진 지역에 디저트 카페가 모여 있다.

원 안의 숫자는 해당 디저트 카페에서 팔고 있는 디저트의 종류를 의미하고

카페들 사이에는 대각선 방향으로 움직일 수 있는 길들이 있다.

디저트 카페 투어는 어느 한 카페에서 출발하여

[Fig. 2]와 같이 대각선 방향으로 움직이고 사각형 모양을 그리며 출발한 카페로 돌아와야 한다.

디저트 카페 투어를 하는 도중 해당 지역을 벗어나면 안 된다.

또한, 친구들은 같은 종류의 디저트를 다시 먹는 것을 싫어한다.

즉, [Fig. 3]과 같이 카페 투어 중에 같은 숫자의 디저트를 팔고 있는 카페가 있으면 안 된다.

[Fig. 4]와 같이 하나의 카페에서 디저트를 먹는 것도 안 된다.

[Fig. 5]와 같이 왔던 길을 다시 돌아가는 것도 안 된다

친구들과 디저트를 되도록 많이 먹으려고 한다.

디저트 가게가 모여있는 지역의 한 변의 길이 N과 디저트 카페의 디저트 종류가 입력으로 주어질 때,

임의의 한 카페에서 출발하여 대각선 방향으로 움직이고

서로 다른 디저트를 먹으면서 사각형 모양을 그리며 다시 출발점으로 돌아오는 경우,

디저트를 가장 많이 먹을 수 있는 경로를 찾고, 그 때의 디저트 수를 정답으로 출력하는 프로그램을 작성하라.

만약, 디저트를 먹을 수 없는 경우 -1을 출력한다.

< ❓ 생각 >

< 💻 코드 >

# n : 회전 횟수, (ci,cj) : 현재 위치, v : 방문한 곳 표시, cnt : 디저트 종류 수
def DFS(n,ci,cj,v):
    # (i,j) : 출발 위치
    global i,j,ans
    
    # 절반을 갔을 때 가지치기
    if n == 2 and ans>=len(v)*2:
        return

    if n > 3 : # 종료조건
        return
        
    # 정답 갱신
    # 회전 3번, 복귀, 디저트 종류 수 최대
    if n == 3 and ci == i and cj == j and ans < len(v):
        ans = len(v)
        return
        
    # 직진 or 방향 바꾸기
    for k in range(n,n+2):
        ni,nj = ci + di[k], cj + dj[k]
        # 범위 내, 중복 아니면
        if 0<=ni<N and 0<=nj<N and arr[ni][nj] not in v:
            v.append(arr[ni][nj])
            DFS(k,ni,nj,v)
            v.pop()

# 4번째 방향 바꾸기 : 복귀 못하므로 실패
di,dj = (1,1,-1,-1,0),(-1,1,1,-1,0)

# 테스트 케이스 개수
T = int(input())
for tc in range(1,T+1):
    # 지역의 한 변의 길이
    N = int(input())
    arr = [list(map(int,input().split())) for _ in range(N)]

	# 방문한 디저트 종류 수
    ans = -1
    # 범위 확인!!
    for i in range(0,N-2):
        for j in range(1,N-1):
            DFS(0,i,j,[])

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

< ❗ 느낀 점 >

너무너무 어려웠다.... 겨우겨우 푼 문제...