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

문제 보러 가기!

DFS로 풀었다.

그대로 직진하거나, 방향을 바꾸거나!! 이때 시계방향이든 반시계방향이든 한 방향으로 돌아봐야 한다~

대각선 방향으로 가야 하고, 두 개(카페, 디저트)의 방문 체크를 고려하는 게 특이했다~

# 대각선 방향
directions = [(1, 1), (1, -1), (-1, -1), (-1, 1)]


def dfs(i, j, direction_type, dessert_cnt):
    global ans

    # 직진 or 꺾기
    if direction_type < 3:
        tmp = direction_type + 2
    else:
        tmp = direction_type + 1

    for k in range(direction_type, tmp):
        ni = i + directions[k][0]
        nj = j + directions[k][1]

        if start[0] == ni and start[1] == nj:  # 왔던 곳으로 돌아옴
            ans = max(ans, dessert_cnt)
            return

        # 범위 벗어나면 X
        if 0 <= ni < N and 0 <= nj < N:
             # 방문하지 않은 카페 & 먹지 않은 디저트
            if cafe_visited[ni][nj] == False and dessert_visited[arr[ni][nj]] == False: 

                # 방문 체크
                cafe_visited[ni][nj] = True
                dessert_visited[arr[ni][nj]] = True

                dfs(ni, nj, k, dessert_cnt + 1)

                # 복구
                cafe_visited[ni][nj] = False
                dessert_visited[arr[ni][nj]] = False


T = int(input())

for tc in range(1, T + 1):
    N = int(input())
    arr = list(list(map(int, input().split())) for _ in range(N))

    cafe_visited = [[False] * N for _ in range(N)]
    dessert_visited = [False] * 101
    ans = -1

    for i in range(N):
        for j in range(N):
            start = (i, j)
            cafe_visited[i][j] = True
            dessert_visited[arr[i][j]] = True

            dfs(i, j, 0, 1)

            cafe_visited[i][j] = False
            dessert_visited[arr[i][j]] = False

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

수정...

'두 개(카페, 디저트)의 방문 체크를 고려하는 게 특이했다~' 라고 했는데..ㅠㅠ
디저트만 방문 체크하면 되고, 카페는 방문 체크할 필요가 없었다..! 4방향 모두 탐색하는 게 아니라서 빙빙 돌 일을 없으니까.. 그걸 빼도 잘 동작한다.

import sys

sys.stdin = open('2105.txt')

# 대각선 방향
directions = [(1, 1), (1, -1), (-1, -1), (-1, 1)]


def dfs(i, j, direction_type, dessert_cnt):
    global ans

    # 직진 or 꺾기
    if direction_type < 3:
        tmp = direction_type + 2
    else:
        tmp = direction_type + 1

    for k in range(direction_type, tmp):
        ni = i + directions[k][0]
        nj = j + directions[k][1]

        if start[0] == ni and start[1] == nj:  # 왔던 곳으로 돌아옴
            ans = max(ans, dessert_cnt)
            return

        # 범위 벗어나면 X
        if 0 <= ni < N and 0 <= nj < N:
            if dessert_visited[arr[ni][nj]] == False:  # 방문하지 않은 카페 & 먹지 않은 디저트

                dessert_visited[arr[ni][nj]] = True

                dfs(ni, nj, k, dessert_cnt + 1)

                dessert_visited[arr[ni][nj]] = False


T = int(input())

for tc in range(1, T + 1):
    N = int(input())
    arr = list(list(map(int, input().split())) for _ in range(N))

    dessert_visited = [False] * 101
    ans = -1

    # 사각형 모양을 그리며 출발하고 카페로 돌아와야 함.

    for i in range(N):
        for j in range(N):
            start = (i, j)
            dessert_visited[arr[i][j]] = True

            dfs(i, j, 0, 1)

            dessert_visited[arr[i][j]] = False

    print(f'#{tc} {ans}')
    ```