[SWEA] 2105. 디저트 카페 (Python)

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

SW Expert Academy

 

def dfs(num, cy, cx, visit):
    global Max, sy, sx
    if num > 3:
        return
    if num == 3 and cy == sy and cx == sx:
        if Max < len(visit):
            Max = len(visit)
            return

    for idx in range(num, num+2): # 현재 방향, 현재방향+1
        dy, dx = cy+directy[idx], cx+directx[idx]
        if 0 <= dy < n and 0 <= dx < n:
            if arr[dy][dx] not in visit:
                visit.append(arr[dy][dx])
                dfs(idx, dy, dx, visit)
                visit.pop()

t = int(input())

for tc in range(1, t+1):
    n = int(input())
    arr = [list(map(int, input().split())) for _ in range(n)]
    Max = -1
    directy = [1, 1, -1, -1, 100] # 4번째는 인덱스를 벗어날 경우를 대비해서 아무 숫자나
    directx = [-1, 1, 1, -1, 100]
    for y in range(n-2):
        for x in range(1, n-1): # 0열과 n-1열은 사각형 생성 불가능
            sy, sx = y, x # 시작점 변수 만들어 주기
            dfs(0, sy, sx, []) # 방향, y좌표, x좌표, visit
    print(f'#{tc} {Max}')

 

💥 주의

• 하............^^
• DFS를 이렇게도 활용할 수 있구나 또 배웠다ㅠㅠ
• 꼭 한 번 더 풀어볼 것