[SWEA] 2105. 디저트 카페

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5VwAr6APYDFAWu#;return%20false; 

SW Expert Academy

일단은 까만색으로 표시한 사각형을 돌 때, 시계방향으로 돌든 시계 반대방향으로 돌든 답은 똑같다. 따라서 방향은 무조건 하나로 고정시키고 돈다. 방향을 전하기 전에 짚고 넘어가야 할 것이 있는데, 위 그림의 사각형은 네 꼭짓점 모두에서 만들 수 있기 때문에 중복이 생길 수 있게 된다. 이를 방지하기 위해서 위에서 아래로 차례대로 탐색하며, 순회하는 순서도 하나로 정해주어야 한다.

위에서 아래로 차례대로 탐색할 때 가장 효율적으로 돌아볼 수 있는 것은 위와 같은 순서이다. 맨 윗 줄은 위를 탐색할 수 없으므로 무조건 아래로 내려가야하며, 맨 왼쪽에서부터 시작하면 좌하단으로 내려갈 수 있는 길도 없으며, 왼쪽에서 두번째 칸이라도 좌하단으로 내려갈 수 있는 칸이 단 하나밖에 존재하지 않는다. 이를 통해 우하단부터 순서대로 방문하며 시계방향으로 도는 것이 최선임을 알 수 있다. 또한 0번째 열과 n-1 번째 열, n-1번째 행은 굳이 살펴보지 않아도 된다는 것을 알 수 있다. 우하단부터 순서대로 시계방향으로 돌기 위해 delta 값 또한 우하단, 좌하단, 좌상단, 우상단 순서로 적어준다.

 

같은 수의 디저트를 판매하는 곳에서 디저트를 먹을 수 없으므로 desert 개수를 인덱스로하는 desert 리스트를 만들어준다. 이외에는 따로 방문 배열을 만들어줄 필요가 없다. 

 

일단 이중 for문을 돌며 양 끝열과 마지막 행을 제외한 모든 가게에 방문하며 solve() 함수로 재귀를 이용한 완전탐색을 진행한다. solve는 방문한 가게 수를 저장할 answer 와 현재 방문한 행과 열을 나타내는 si, sj, 시작한 위치를 나타내는 start, 순서를 나타내는 dire을 매개변수로 받는다.

 

처음에는 무조건 우하단으로 이동하기 때문에 solve 함수에 현재 행+1, 현재 열 +1 을 해준 뒤 넘겨준다. 재귀를 계속 타고 들어가며 지금 좌표가 시작점과 같으면 최대 가게 개수를 갱신해주고 return, 현재 좌표가 접근할 수 없다면 또 return 해주는 base case을 적어준다.

 

또한 현재 좌표에 위치한 가게의 디저트 개수가 이미 먹은 디저트 개수이면 return 해주고 아니라면 방문 표시 후, 방향을 유지한 채 재귀를 타고 들어가는 경우, 방향을 바꿔서 재귀를 타고 들어가는 경우 두 개를 진행해주고 다시 방문 표시를 지워준다.

 

방향을 하나로 고정시키면 된다는 아이디어를 떠올리는 게 관건인 문제다.

재귀를 좀 더 확실히 이해할 수 있는 문제였다.

 

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


def solve(answer, si, sj, start, dire):
    global max_answer
    if (si, sj) == start:
        max_answer = max(max_answer, answer)
        return
    if si < 0 or sj < 0 or si >= n or sj >= n:
        return

    if desert[maps[si][sj]]: # 이미 먹은 곳
        return
 
    else:
        desert[maps[si][sj]] = 1
        solve(answer+1, si+dy[dire], sj+dx[dire], start, dire)
        if dire+1 < 4:
            solve(answer+1, si+dy[dire+1], sj+dx[dire+1], start, dire+1)
        desert[maps[si][sj]] = 0


for tc in range(1, int(input())+1):
    n = int(input())
    maps = [list(map(int, input().split())) for _ in range(n)]
    desert = [0]*101
    max_answer = -1
    for i in range(n-1):
        for j in range(1, n-1):
            desert[maps[i][j]] = 1
            solve(1, i+1, j+1, (i, j), 0)
            desert[maps[i][j]] = 0
    print('#{} {}'.format(tc, max_answer))