[SWEA] 디저트 카페 (모의 SW 역량테스트) / python

1. 문제 설명

친구들과 디저트 카페 투어를 할 계획이다.
한 변의 길이가 N인 정사각형 모양을 가진 지역에 디저트 카페가 모여 있다.

 

원 안의 숫자는 해당 디저트 카페에서 팔고 있는 디저트의 종류를 의미하고 카페들 사이에는 대각선 방향으로 움직일 수 있는 길들이 있다.

 

• 디저트 카페 투어는 어느 한 카페에서 출발하여 대각선 방향으로 움직이고 사각형 모양을 그리며 출발한 카페로 돌아와야 한다.
• 디저트 카페 투어를 하는 도중 해당 지역을 벗어나면 안 된다.
• 또한, 친구들은 같은 종류의 디저트를 다시 먹는 것을 싫어한다.
  카페 투어 중에 같은 숫자의 디저트를 팔고 있는 카페가 있으면 안 된다.
• 하나의 카페에서 디저트를 먹는 것도 안 된다.
• 같이 왔던 길을 다시 돌아가는 것도 안 된다.

 

친구들과 디저트를 되도록 많이 먹으려고 한다.

디저트 가게가 모여있는 지역의 한 변의 길이 N과 디저트 카페의 디저트 종류가 입력으로 주어질 때,

임의의 한 카페에서 출발하여 대각선 방향으로 움직이고

서로 다른 디저트를 먹으면서 사각형 모양을 그리며 다시 출발점으로 돌아오는 경우,

디저트를 가장 많이 먹을 수 있는 경로를 찾고, 그 때의 디저트 수를 정답으로 출력하는 프로그램을 작성하라.

만약, 디저트를 먹을 수 없는 경우 -1을 출력한다.

 

[제약사항]

1. 시간제한 : 최대 50개 테스트 케이스를 모두 통과하는 데 C/C++/Java 모두 3초
2. 디저트 카페가 모여있는 지역의 한 변의 길이 N은 4 이상 20 이하의 정수이다. (4 ≤ N ≤ 20)
3. 디저트 종류를 나타나는 수는 1 이상 100 이하의 정수이다.

 

[입력]

입력의 맨 첫 줄에는 총 테스트 케이스의 개수 T가 주어지고, 그 다음 줄부터 T개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 디저트 카페가 모여있는 지역의 한 변의 길이 N이 주어진다.

그 다음 N 줄에는 N * N 크기의 디저트 카페에서 팔고 있는 디저트 종류에 대한 정보가 주어진다.

 

[출력]

테스트 케이스 개수만큼 T개의 줄에 각각의 테스트 케이스에 대한 답을 출력한다.

각 줄은 "#t"로 시작하고 공백을 하나 둔 다음 정답을 출력한다. (t는 1부터 시작하는 테스트 케이스의 번호이다)

출력해야 할 정답은 가능한 경우 중 디저트를 가장 많이 먹을 때의 디저트 수 이다.

만약, 디저트를 먹을 수 없는 경우 정답은 -1이다.

 

2. 풀이 전 계획과 생각

입력

• N → 지역의 한 변의 길이
• desert_kinds → N * N 크기의 디저트 카페에서 팔고 있는 디저트 종류 (2차원 배열)

구하고자 하는 바

가장 많이 먹을 수 있는 경로를 찾고, 그때 디저트의 수를 출력

설계

• 모든 격자에서 기울어진 직사각형 탐색을 하자.
  • 대각선 방향
    • dys = [-1, -1, 1, 1]
    • dxs = [ 1, -1, -1, 1]
• 디저트 수의 최댓값 갱신하자.
• 예외
  • 도중 해당 지역을 벗어나면 안된다.
    • in_range ⇒ 0 ≤ y < N, 0 ≤ x < N
  • 카페 투어 중에 같은 숫자의 디저트를 팔고 있는 카페가 있으면 안된다.
  • (만약에 먹을 수 없는 경우 -1 출력)

필요한 함수

explore(r, c) : 현재 위치에서 기울어진 직사각형 탐색하는 함수

 

3. 풀이

def init():
    input_n = int(input())
    input_grid = [list(map(int, input().split())) for _ in range(input_n)]
    input_unique_desert = []
    return input_n, input_grid, input_unique_desert

def in_range(y, x):
    return 0 <= y < N and 0 <= x < N

def explore(y, x, k, l):
    dys, dxs = [-1, -1, 1, 1], [1, -1, -1, 1]
    move_nums = [k, l, k, l]

    result = 0
    global unique_desert

    for dy, dx, move_num in zip(dys, dxs, move_nums):
        for _ in range(move_num):
            y, x = y + dy, x + dx
            if not in_range(y, x):
                return 1

            unique_desert.append(grid[y][x])
            result += 1

    if len(unique_desert) != len(set(unique_desert)):
        return 1

    return result

def pro():
    max_count = 0
    for y in range(N):
        for x in range(N):
            for k in range(1, N):
                for l in range(1, N):
                    global unique_desert
                    unique_desert = []
                    max_count = max(max_count, explore(y, x, k, l))

    return max_count

for test_case in range(1, int(input()) + 1):
    N, grid, unique_desert = init()
    answer = pro()

    if answer == 1:
        answer = -1
    print(f'#{test_case} {answer}')

 

4. 풀이 후 알게된 개념과 소감

• 자기 자신에게 되돌아온다는 말은 결국 기울어진 직사각형 탐색을 의미한다.
• 중복되는 경우를 확인할 때 set을 사용하면 된다.