[SWEA] 2105. 디저트 카페

문제

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

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

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

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

1. 겹치는 숫자가 있으면 안 됨
2. 반드시 네 방향을 다 돌아야 함

풀이(딕셔너리)

• 처음에 24개만 맞았는데 이유는 재귀를 돌리면서 한 번 갔다가 되돌아올 때 그 카페를 방문하지 않았다는 처리를 안 해줬기 때문에

def dfs(r, c, idx, cnt):
    global maxV
    if idx == 4:
        return
    elif idx == 3 and (r, c) == (i, j):
        if maxV < cnt:
            maxV = cnt
        return

    dr, dc = r + dx[idx], c + dy[idx]
    if -1 < dr < N and -1 < dc < N:
        if dessert.get(arr[dr][dc]):
            return
        else:
            dessert[arr[dr][dc]] = 1
            dfs(dr, dc, idx, cnt+1)
            dfs(dr, dc, idx+1, cnt+1)
    else:
        return
    del dessert[arr[dr][dc]]

T = int(input())
for tc in range(1, T+1):
    N = int(input())
    arr = [list(map(int, input().split())) for _ in range(N)]

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

    maxV = -1
    for i in range(N-2):
        for j in range(1, N-1):
            dessert = {}
            dfs(i, j, 0, 0)
                
    print(f'#{tc}', maxV)

풀이(리스트)

• 걍 리스트가 훨씬 빠름
• 추가로 출발점 카페의 디저트 숫자를 넣고 시작하면 자꾸 에러가 났는데 출발점 숫자가 이미 있으면 dr, dc로 재귀를 돌릴 때 이미 숫자가 있는 곳은 방문하지 않기 때문에 출발점으로 되돌아갈 수 없기 때문

def dfs(r, c, idx, cnt):
    global maxV
    if idx == 4:
        return

    dr, dc = r + dx[idx], c + dy[idx]
    if (dr, dc) == (i, j):
        if maxV < cnt:
            maxV = cnt + 1
        return

    if -1 < dr < N and -1 < dc < N:
        if dessert[arr[dr][dc]]:
            return
        else:
            dessert[arr[dr][dc]] = 1
            dfs(dr, dc, idx, cnt+1)
            dfs(dr, dc, idx+1, cnt+1)
            dessert[arr[dr][dc]] = 0
    else:
        return

T = int(input())
for tc in range(1, T+1):
    N = int(input())
    arr = [list(map(int, input().split())) for _ in range(N)]
    dessert = [0] * 101

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

    maxV = -1
    for i in range(N-2):
        for j in range(1, N-1):
            dessert[arr[i][j]] = 1
            dfs(i, j, 0, 0)
            dessert[arr[i][j]] = 0
                
    print(f'#{tc}', maxV)