[SWEA] 2105. [모의 SW 역량테스트] 디저트 카페

이해도

★☆☆☆☆ 지못미..

소감

• DFS, 백트래킹을 사용하는 문제로 난이도 높게 느껴졌다.
• 위의 알고리즘을 사용하지 않고 푸는 것도 가능하다. 왼쪽과 오른쪽 갈 수 있는 거리를 구해 조건을 걸어주는 식이다.
• DFS, 백트래킹 이해 후 다시 도전하는 것이 좋겠다.

접근방식 유형1

• 방향은 한쪽 방향으로만 돌아도 괜찮다.
• 백트래킹으로 분기처리를 하기 => d, d+1인 이유는 두 방향(우-하 방향으로 진행중이었다면 우-하 와 좌-하) 으로 가면 되기 때문이다.
• map 함수를 사용하여 이중리스트 내에 있는 리스트들의 길이를 routes에 담는다.
• DFS 처럼 끝까지 갔다가 돌아오는건 아니고, 함수 리턴값 없이 가지치기 하며 뻗어나가는 구조이다.

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

dx1 = [1, 1, -1, -1]  # ↘, ↙, ↖, ↗
dy1 = [1, -1, -1, 1]  # 시계방향


def backtracking(x, y, cafe_route, menu, d):
    global routes, desserts
    if d == 4:
        if cafe_route and cafe_route[0] == (x, y):
            routes.append(cafe_route[:])
            desserts.append(menu[:])
        return

    if cafes[x][y] in menu:
        return

    else:
        nx = x + dx1[d]
        ny = y + dy1[d]
        
        if -1 < nx < N and -1 < ny < N:
            backtracking(nx, ny, cafe_route + [(x, y)], menu + [cafes[x][y]], d)   # 분기처리
            backtracking(nx, ny, cafe_route + [(x, y)], menu + [cafes[x][y]], d+1) # 분기처리
        else:
            return
        
        
T = int(input())


for tc in range(1, T + 1):
    N = int(input())  # 배열 크기
    cafes = [list(map(int, input().split())) for _ in range(N)]
    # 길을 저장할 리스트, 디저트 종류를 저장할 리스트를 선언한다.
    routes = []
    desserts = []

    for i in range(N):
        for j in range(N):
            backtracking(i, j, [], [], 0)

    # 루트에 값이 있다면 최대 방문횟수를, 없다면 -1을 출력한다.
    routes = list(map(len, routes)) 
    result = -1
    if routes:
        result = max(routes)

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

접근방식 유형2

• DFS 를 사용하여 끝까지 갔다가, 확인 후 되돌아오는 방식이다.

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

def dfs(r, c, passed, direction):
    global answer
    tmp_direction = direction
    for i in range(4):
        nr = r + dr[i]
        nc = c + dc[i]
        if 0 <= nr < N and 0 <= nc < N and board[nr][nc] not in passed and visited[nr][nc] == 0:
            if direction <= i <= direction + 1:
                direction_visited[i] = 1
                passed.append(board[nr][nc])
                visited[nr][nc] = 1
                direction = i
                dfs(nr, nc, passed, direction)  # ?????????????
                visited[nr][nc] = 0
                direction = tmp_direction
                passed.remove(board[nr][nc])

        if sum(direction_visited) >= 3 and [nr, nc] == start:
            ans = len(passed)
            answer = max(ans, answer)

#시계
dr = [1, 1, -1, -1]
dc = [1, -1, -1, 1]

for tc in range(1, int(input()) + 1):
    N = int(input())
    board = [list(map(int, input().split())) for _ in range(N)]
    answer = -1
    for i in range(N):
        for j in range(N):
            visited = [[0] * N for _ in range(N)]
            direction_visited = [0] * 4
            start = [i, j]
            dfs(i, j, [board[i][j]], -1)

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

접근방식 유형3

• DFS, 백트래킹을 사용하지 않고 갈 수 있는 왼쪽과 오른쪽 경로의 수를 구한 코드이다.

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


T = int(input())

for t in range(1, T + 1):
    N = int(input())
    board = []
    max_count = -1

    for _ in range(N):
        board.append([int(x) for x in input().split()])

    # 사각형의 위 꼭지점이 될 수 있는 후보들에 대하여, 모든 사각형을 탐색한다.
    for r in range(N - 1):
        for c in range(1, N - 1):
            # left: 왼쪽 아래로 몇 칸 가는지
            # right: 오른쪽 아래로 몇 칸 가는지
            for left in range(1, c + 1):
                for right in range(1, N - c):
                    # 아래쪽 꼭지점이 배열의 범위를 벗어나는 경우
                    if r + left + right >= N:
                        continue

                    numbers = set()
                    numbers.add(board[r][c])

                    nr, nc = r, c
                    # 위 꼭지점에서부터 반시계 방향으로 탐색을 진행한다.
                    # 위 꼭지점 => 왼쪽 꼭지점
                    for _ in range(left):
                        nr, nc = nr + 1, nc - 1
                        numbers.add(board[nr][nc])
                    # 왼쪽 꼭지점 => 아래 꼭지점
                    for _ in range(right):
                        nr, nc = nr + 1, nc + 1
                        numbers.add(board[nr][nc])
                    # 아래 꼭지점 => 오른쪽 꼭지점
                    for _ in range(left):
                        nr, nc = nr - 1, nc + 1
                        numbers.add(board[nr][nc])
                    # 오른쪽 꼭지점 => 위쪽 꼭지점
                    for _ in range(right):
                        nr, nc = nr - 1, nc - 1
                        numbers.add(board[nr][nc])

                    # 직사각형에 포함된 디저트의 종류가 모두 다른 경우 => 조건 만족
                    if len(numbers) == 2 * (left + right):
                        max_count = max(max_count, len(numbers))

    print("#{} {}".format(t, max_count))

출처 : 서울 3반