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

문제

한 카페에서 출발하여 대각선 방향으로 움직이고, 사각형 모양을 그리며 출발한 카페로 복귀. 같은 종류 디저트 중복 안된다.

내 코드

import sys
sys.stdin = open("input.txt","rt")

# nxn 보드, 각 칸의 값은 디저트 종류
# 대각선 방향으로 움직이고 사각형 모양을 그리며 출발한 카페로 돌아와야 한다.
# 최대한 많이 먹고 오려고 한다.
# 왔던 길 다시 못감
# 같은 숫자의 디저트를 팔고 있는 카페가 있으면 안된다.
# 임의의 한 카페에서 출발해 대각선 방향으로 움직이고 서로 다른 디저트를 먹으면서 사각형 모양을 그리며 출발점으로 돌아오는 경우
# 디저트를 가장 많이 먹을 수 있는 경로를 찾고, 그 때의 디저트 수를 출력
# 그 경우 없으면 -1

dx = [1,1,-1,-1]
dy = [-1,1,1,-1] # 순서대로 방향

def isInner(x,y):
    if 0<=x<n and 0<=y<n:
        return True
    return False

def DFS(L, dir,x,y,visited): # 현재 방향도 함께. 현재 방향 기준 직진(방향 유지), 좌회전을 해야하기 때문.
    global res
    if dir > 3: # 무조건 종료 방향은 3번 바꾸면 끝 가지치기 더 바꾸면 끝내야함.
        return
    if dir == 3 and (i,j) == (x,y): # 돌아온 경우
        res = max(res, L)
    else: # 아직 방향전환을 모두 이루지 못함.
        for d in range(2): # 방향 2개만 고려해도 됨
            direction = (dir + d) % 4 # 없을 수도 있으니 일단은 이렇게 진행. 하지만 dir +d로 해도 됨. 이 문제는 넘어갈 수 없기 때문.
            nx = x + dx[direction]
            ny = y + dy[direction]
            if isInner(nx,ny) and g[nx][ny] not in visited:
                visited.append(g[nx][ny])
                DFS(L+1, dir + d, nx,ny,visited)
                visited.pop() # 백트랙킹 시 원상복구




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

    res = -1 # 안되는 경우를 미리 넣어둠.
    for i in range(n):
        for j in range(n):
            DFS(0,0,i,j,[]) # 이 문제의 경우는 방문을 값을 통해 하기 때문에 리스트를 파라미터로 넘겨줌

    print(f"#{t} {res}")

코멘트

가능한 모든 경우 확인 -> DFS. 백트랙킹
1. 전체 배열 순회 (시작점)
2. 3번 꺾고 되돌아 오는 경우 중 중복되지 않고, 몇개를 먹었는지 계속 확인)
3. 선택 : 직진, 좌회전 (어차피 어디로 돌든 똑같기 떄문에 한 방향으로 진행)

정답처리 : 방향은 3번 꺾으면서, 시작지점 복귀한 경우

1. 현재 방향 유지할지 꺾을지 선택

근데 종료 조건은 L == 3일 때 끝내야해. 근데 정답 처리는 3인 지점에서 해주는 거야.

nxn 격자모양 지도, 각 칸에는 디저트 카페 종류
임의의 카페에서 출발해 대각선 방향으로 움직이면서 서로 다른 디저트를 먹고 사각형 모양 그리면서 출발점으로 돌아와야 한다.
같은 종류의 디저트를 팔고 있는 카페는 중복해서 방문할 수 없음
디저트를 가장 많이 먹을 수 있는 경로를 찾고, 그때 먹을 수 있는 디저트의 수 출력

각 칸에서 직진과 좌회전 2가지 방향으로 이동할 수 있다.

• 이렇게 하면 방향을 3번 틀면 사각형을 만듦.

방문한 디저트 종류를 리스트에 저장해 중복 방문 방지 가능

핵심은 DFS어떻게 짤 것인지...

1. 방향 전환이 3번 이상 이루어지면 더 이상 탐색할 필요가 없으므로 종료(가지치기)
2. 방향 전환이 3번 이루어지고 현재 위치가 시작위치와 같다면 사각형 모양으로 순회한 것이므로 res 갱신.
3. 현재 위치에서 직진과 좌회전 2가지 방향에 대해서 계산해야 한다.
4. 방문한 디저트 종류를 visited에 추가하고, DFS 호출이 끝난 후에는(백트랙킹 시) visited 제거해야 한다.

모든 좌표를 시작점으로 하여 계산했어야 했다.