[SW Expert Academy] 2105. 디저트 카페

2105. 디저트 카페

---

문제)

 

친구들과 디저트 카페 투어를 할 계획이다.

[Fig. 1]과 같이 한 변의 길이가 N인 정사각형 모양을 가진 지역에 디저트 카페가 모여 있다.

 

 

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

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

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

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

 

 

디저트 카페 투어를 하는 도중 해당 지역을 벗어나면 안 된다.

또한, 친구들은 같은 종류의 디저트를 다시 먹는 것을 싫어한다.

즉, [Fig. 3]과 같이 카페 투어 중에 같은 숫자의 디저트를 팔고 있는 카페가 있으면 안 된다.

 

 

[Fig. 4]와 같이 하나의 카페에서 디저트를 먹는 것도 안 된다.

 

 

[Fig. 5]와 같이 왔던 길을 다시 돌아가는 것도 안 된다.

 

 

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

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

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

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

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

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

 

 

[예시]

한 변의 길이 N이 4인 지역에 디저트 카페가 [Fig. 6]과 같이 있다고 생각하자.

 

 

디저트 카페 투어가 가능한 경우는 [Fig. 7]과 같이 5가지로 나눌 수 있다.

(출발한 곳과 도는 방향은 다를 수 있지만, 디저트 카페 투어의 경로가 그리는 사각형 모양은 5가지 중 하나이다.)

 

 

이 중에 디저트를 가장 많이 먹을 수 있는 경우는 ⑤인 경우로 디저트의 종류는 6개이다.

따라서, 정답은 6이 된다.

 

 

[제약사항]

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이다.

 

 

 

 

풀이)

다른 분의 더 간결한 코드가 있었는데, 

이 문제를 좀 많이 헤메다보니 이해가 잘 안되서, 내가 할 수 있는 한에서 최대한 풀어보았다.

 

def recur(cur, a, b, cnt):
    global answer
    
    # 시계 반대 방향
    di = [1, 1, -1, -1]
    dj = [-1, 1, 1, -1]
 
    # 변을 4개 다 그었을 때, 처음 자리로 돌아왔다면.
    if cur == 4:
        if a[0] == q and a[1] == w:
            answer = max(answer, cnt)
            return
    
    # 선 긋는 중
    if cur < 4:
        x = a[0] + di[cur]
        y = a[1] + dj[cur]
        # 인덱스 범위 내에서,
        if -1 < x < n and -1 < y < n:
            # 아직 해당 디저트 종류가 없다면,
            if not g[x][y] in b:
                # 방향꺾기 ( cur + 1 )
                recur(cur + 1, [x, y], b + [g[x][y]], cnt + 1)
                # 방향 유지 ( cur )
                recur(cur, [x, y], b + [g[x][y]], cnt + 1)
        else:
            return
 
 
 
T = int(input())
for _ in range(T):
    n = int(input())
    g = [list(map(int, input().split())) for i in range(n)]
 
    answer = 0
    # 사각형이 만들어 질 수 있는 인덱스들
    for i in range(n - 2):
        for j in range(1, n - 1):
            # 돌아왔는지 확인하기 위해
            q, w = i, j
            recur(0, [i, j], [], 0)
 
    if answer:
        print(f"#{_ + 1} {answer}")
    else:
        print(f"#{_ + 1}", -1)

---

문제 출처 : https://swexpertacademy.com/main/main.do

SW Expert Academy

※ SW Expert 아카데미는 원칙적으로 문제를 무단 복제하는 것을 금지합니다.

학습용으로 문제를 가져왔으나, 문제가 될 시 수정 및 삭제하겠습니다.