SW Expert Academy - 디저트카페 (python)

❓ 문제 - SW Expert Academy 디저트카페  python 풀이법

 

출처 

(https://swexpertacademy.com/main/solvingProblem/solvingProblem.do)

SW Expert Academy

 

다른 분의 코드 참조하여 해결하였습니다...

(https://dongsik93.github.io/algorithm/2019/07/04/algorithm-swexpert-sw2105/)

SW expert 2105 디저트 카페문제-python - 동식이 블로그

 

 

📝 문제해결법

1. 이 문제는 완전탐색(DFS)+구현로 풀었다.

• 문제에서 모든 행과 열을 돌면서 사각형(오른쪽아래-왼쪽아래,왼쪽위,오른쪽 위 순서로)을 그릴 수 있는지 DFS로 검사한다.
• 우선 문제에서 주어진 조건에서 사각형을 그린 후 마지막으로 처음시작점에 다시 돌아와야 하므로 시작점 sx, sy를 전역 변수로 선언한다.
• 또한 문제에서 주어진 조건에서 사각형을 그릴 때, 디저트 카페의 종류가 중복되면 안되기 때문에 사각형을 그릴 때마다 리스트에 해당 디저트 종류의 수를 넣어준다. DFS로 사각형을 다 그린 후, 다시 리스트에 디저트 종류의 수를 빼준다.
• DFS를 돌릴 때, 사각형을 완성한 기준은 그전에 이동한 방향(d)가 3(오른쪽 위)이고, 이동한 위치가 시작점과 같으면 해당 사각형에 들어간 카페의 수의 최대값을 갱신한다.
• 만약 그전에 이동 방향에 따라 이동한 위치가 격자칸 범위에 벗어나면 사각형을 그리지 못하므로 리턴한다.
• 만약 그전에 이동 방향에 따라 이동한 위치가 이미 디저트의 수에 중복되는 곳이라면 사각형을 그리지 못하므로 리턴한다.
• 그 후에는 사각형을 그리기 위해 이동처리 해야하므로 방문 리스트에 이동한 카페의 디저트 수를 넣어주고, 이전 이동 방향을 기준으로 0, 1(오른쪽 아래, 왼쪽 위) 이면 자신의 방향을 유지한채 이동 시키거나, 방향 +1 해준 상태로 사각형을 그리기 위해 DFS를 호출한다.
• 만약 이전 이동한 방향이 2(왼쪽 위)이면 만약 시작 위치와 행,열이 반대일 땐 사각형을 그리기 위해서 무조건 방향을 +1해주고 이동시켜 사각형을 그리고, 아직 시작위치와 행,열이 반대가 아니라면 2방향으로 한칸 더 이동처리 하여 사각형을 그린다.
• 만약 이전 이동한 방향이 3(오른쪽 위)라면 해당 방향을 유지한채 이동해서 사각형을 그릴 수 있으므로 DFS를 호출한다.

2. 문제 풀면서 느낀점

• 처음 기본 DFS 방식만으로 사각형을 그리려고 했다가 실패하였다... 사각형을 구현하는 방법을 꼭 기억해두자..^^

 

💻 소스코드

T = int(input())
dx = [1, 1, -1, -1]
dy = [1, -1, -1, 1]

def dfs(num, x, y, d):
    global max_cafe
    global sx, sy
    if d == 3 and x == sx and y == sy:
        max_cafe = max(max_cafe, num)
        return
    elif not (0<=x<n and 0<=y<n):
        return
    elif board[x][y] in visited:
        return
    else:
        visited.append(board[x][y])
        if d in [0, 1]:
            dfs(num+1, x+dx[d], y+dy[d], d)
            dfs(num+1, x+dx[d+1], y+dy[d+1], d+1)
        elif d == 2:
            if x + y != sx + sy:
                dfs(num+1, x+dx[2], y+dy[2], 2)
            else:
                dfs(num+1, x+dx[3], y+dy[3], 3)
        else:
            dfs(num+1, x+dx[3], y+dy[3], 3)
        visited.remove(board[x][y])
    return


for test_case in range(1, T+1):
    n = int(input())
    board = [list(map(int, input().split())) for _ in range(n)]
    max_cafe = -1
    visited = []
    for i in range(n):
        for j in range(n-1):
            sx, sy = i, j
            visited.append(board[i][j])
            dfs(1, i+1, j+1, 0)
            visited.remove(board[i][j])

    print(f'#{test_case} {max_cafe}')