SW Expert Academy 2105. [모의 SW 역량테스트] 디저트 카페 풀이 With Python

문제 링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5VwAr6APYDFAWu&categoryId=AV5VwAr6APYDFAWu&categoryType=CODE

SW Expert Academy

이 문제를 bfs(너비 우선 탐색) 기법으로 해결하였다. 가장 먼저 시작할 때 방향을 오른쪽 아래로 방향을 고정하고, 이후에 큐에 지나간 포인트 값과 마지막 방향을 저장하여서 방향이 바뀔 때마다 count값을 늘렸고, 방향이 바뀐 횟수가 4번이고, 제자리로 돌아왔을 때 지나온 포인트의 개수를 answer값과 비교하여 업데이트하였다. 아래는 문제를 해결한 코드이다.

from collections import deque

t = int(input())
dx = [-1, 1, 1, -1]
dy = [-1, -1, 1, 1]
for test in range(1, t + 1):
    answer = -1
    n = int(input())
    map1 = [list(map(int, input().split())) for _ in range(n)]
    for i in range(n):
        for j in range(n):
            queue = deque()
            queue.append([i, j, [map1[i][j]], 0, -1])
            while queue:
                x, y, shops, count, ld = queue.popleft()
                if x == i and y == j and count == 4:
                    if answer < len(shops):
                        answer = len(shops)
                elif count == 0:
                    nx = x + dx[2]
                    ny = y + dy[2]
                    if -1 < nx < n and -1 < ny < n and map1[nx][ny] != map1[i][j]:
                        queue.append([nx, ny, shops + [map1[nx][ny]], 1, 2])
                elif count < 5:
                    for d in range(4):
                        nx = x + dx[d]
                        ny = y + dy[d]
                        if -1 < nx < n and -1 < ny < n:
                            if nx == i and ny == j and count>1:
                                if ld == d:
                                    queue.append([nx, ny, shops, count, d])
                                else:
                                    queue.append([nx, ny, shops, count + 1, d])
                            elif map1[nx][ny] not in shops:
                                if ld == d:
                                    queue.append([nx, ny, shops + [map1[nx][ny]], count, d])
                                else:
                                    queue.append([nx, ny, shops + [map1[nx][ny]], count + 1, d])

    print('#{} {}'.format(test, answer))