[SWEA 2105] 파이썬 - 디저트카페

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5VwAr6APYDFAWu

SW Expert Academy

 

 

 

# 조건

• N x N 모양의 지역에 디저트 카페가 모여있다.
• 칸의 숫자는 디저트의 종류를 뜻하며 카페들 사이에는 대각선 방향으로만 이동 가능
• 대각선으로 카페 투어를 떠난 후 다시 처음 카페로 돌아오면 된다.
• 이때, 한 번 먹은 종류의 디저트 카페는 갈 수 없고, 왔던 길도 돌아갈 수 없다.

 

 

# 접근 방법

 

#1 dfs

• dfs를 이용하여 사각형을 그려주며 탐색할 수 있다.
• 회전 방향을 정하고, 카페와 디저트 종류를 방문했는지 표시하는 배열 작성
• 이차원 배열에서 대각 선에 있는 칸은 좌표 x, y의 합이 같다!!

import sys
sys.stdin = open('input.txt', 'r')


def ds(i, j, k, n):  # k는 방향, n 은 진행한 칸수
    global copy_i, copy_j, max_val
    if k == 3 and i == copy_i and j == copy_j:  # 출발점에 도착한경우
        if max_val < n:
            max_val = n
    elif i < 0 or i >= N or j < 0 or j >= N:  # 범위 밖
        return
    elif arr[i][j] in path:  # 숫자가 겹친경우
        return
    else:  # 갈 수 있는곳
        path.append(arr[i][j])
        if k == 0 or k == 1:  # 오른쪽 방향 그대로 가거나 왼쪽으로 꺾었을 경우에
            ds(i + di[k], j + dj[k], k, n + 1)  # 방향 그대로 쭉 가는것
            ds(i + di[k + 1], j + dj[k + 1], k + 1, n + 1)  # 방향 꺾음
        elif k == 2:
            if i + j != copy_i + copy_j:  # 출발점을 향하는게 아님 ( 도착할 수 있는 경우가 아닐 때 )
                ds(i + di[2], j + dj[2], k, n + 1)  # 그냥 쭉 가
            else:    # ( 도착할 수 있는 경우일 때 )
                ds(i + di[3], j + dj[3], k + 1, n + 1)  # 방향 꺾어서 가
        else:  # k가 3일때는 직진한다.
            ds(i + di[3], j + dj[3], k, n + 1)
        path.pop()


for tc in range(1, int(input())+1):
    N = int(input())
    arr = [list(map(int, input().split())) for _ in range(N)]
    max_val = -1
    path = []
    # 오른쪽 아래, 왼쪽 아래, 왼쪽 위, 오른쪽 위
    di = [1, 1, -1, -1]
    dj = [1, -1, -1, 1]
    for i in range(N):
        for j in range(1, N - 1):
            copy_i = i
            copy_j = j
            path.append(arr[i][j])
            ds(i + 1, j + 1, 0, 1)
            path.pop()

    print("#{} {}".format(tc, max_val))

 

#2 bfs

 

• dfs와 비슷하지만 재귀 대신 queue를 이용하여 풀어주었다.
• 내가 진행하고 있는 방향, 방향 전환 횟수, 디저트 종류, 출발지점에 대한 정보를 담아준다.
• 방향 전환을 4번 하였고 출발지와 인덱스가 동일하다면 최댓값 갱신
• 중요한 점은 진행방향 확인인데 사각형을 만들며 내가 이전에 이동하였던 방향 (예를 들어 우하)은 다시 가지 않도록 델타 함수 인덱스를 저장해주었다.
• 또한, 델타함수 방향을 시계방향으로 고정해주며 비교해주었음!

# N x N 모양의 지역에 디저트 카페 모여있다.
# 칸의 숫자는 디저트의 종류
# 카페들 사이에는 대각선 방향 길
# 대각선으로 사각형 모양을 그리며 출발한 카페로 돌아와야한다.

# 같은 종류의 디저트를 먹는 것 싫어한다.
# 한 곳도 안됨, 왔던길도 못돌아감

# 디저트 가장 많이 먹는 경로, 그 때의 디저트 수 출력
# 먹을 수 없는 경우 -1
import sys
from collections import deque
sys.stdin = open('input.txt')


T = int(input())
for tc in range(1, T+1):
    N = int(input())
    # 초기값 - 먹을수 없는 경우
    result = -1
    # 갈 수 있는 대각선 체크해주고
    # 디저트 종류 리스트에 넣어주기
    # 중간에 한 곳이라도 디저트가 겹친다면 다른 루트 찾아준다.
    cafe = [list(map(int, input().split())) for _ in range(N)]

    # 방향 고정 -> 우하, 좌하, 좌상, 우상
    dx, dy =[1,1, -1, -1], [1, -1, -1, 1]

    for i in range(N):
        for j in range(N):
            q = deque()
            # 출발 위치, 디저트의 종류, 회전 카운트, 델타함수 인덱스 = 지나간 방향
            q.append([i, j, [cafe[i][j]], 0, -1])
            while q:
                x, y, dessert, count, ld = q.popleft()
                # 처음 출발위치로 돌아 왔다면 최댓값 갱신
                if x == i and y == j and count == 4:
                    if result < len(dessert):
                        result = len(dessert)

                # 아직 사각형을 그리지 못했다면
                elif count < 5:
                    # 4방향 탐색
                    for d in range(4):
                        # 지금 탐색 가능한 방향이  이전의 방향이 아니라면 -> 우하로 왔는데 또 우하 탐색하면 사각형 불가
                        if d >= ld:
                            nx, ny = x + dx[d], y + dy[d]

                            # 탐색 가능 지역이라면
                            if 0 <= nx < N and 0 <= ny < N:
                                # 1번 이상 꺾고 도착했다면
                                if nx == i and ny == j and count>1:
                                    # 이전에 지나온 방향이 같다면 -> 꺾지 않았다면 count 그대로
                                    # 아니라면 count +1
                                    # 확인하기 위한 append
                                    if ld == d:
                                        q.append([nx, ny, dessert, count, d])
                                    else:
                                        q.append([nx, ny, dessert, count+1, d])
                                 # 중복 디저트 없다면
                                elif cafe[nx][ny] not in dessert:
                                    # 이전에 지나온 방향이 같다면 -> 꺾지 않았다면 count 그대로
                                    # 아니라면 count +1
                                    # 지금 먹으러가는 디저트 + 현재까지 먹은 디저트 종류
                                    if ld == d:
                                         q.append([nx, ny, dessert + [cafe[nx][ny]], count, d])
                                    else:
                                        q.append([nx, ny, dessert + [cafe[nx][ny]], count +1, d])

    print(f'#{tc} {result}')

 

 

• 난이도가 어려워질수록 시작점과 의사 코드 작성이 중요한 것 같다.
• 또한 이번 문제의 경우 dfs가 좋아 보이지만, 재귀에 약하다는 이슈로 bfs로 먼저 풀게 되었다.
• 부족한 부분에 대해선 집중적으로 트레이닝할 필요가 있는 듯하다.