[SWEA] 2105_디저트 카페 (DFS 이용)

📕 문제

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

SW Expert Academy

 

💡 풀이법

: dfs로 풀었는데 확실히 재귀보다 stack을 이용해서 푸는게 훠~~~얼씬 빨랐다..👍

 

1. 대각선 방향으로 움직이기 때문에 4방향의 대각선 방향을 dxy로 만들어준다.

2. 어디서 시작할지 모르기 때문에 2중 for문을 돌며서 시작점을 매번 바꿔가면 dfs를 돌려준다.

3. 그런데 매번 4개의 대각선 방향을 다 탐색해줄 필요가 없는게 어차피 윗방향의 대각선은 for문을 돌며서 검사를 다 했기 때문에 봐줄 필요가 없다. 그리고 왼쪽 아래로 갈지 오른쪽 아래로 갈지도 어차피 사각형을 시계 방향으로 돌지 반시계 방향으로 돌지만 다를뿐이지 결국 같은 위치를 방문하는 꼴이기 때문에 움직이는 방향의 순서를 아래와 같이 항상 고정시켜놔도 된다.

오른쪽 아래 -> 왼쪽 아래 -> 왼쪽 위 -> 오른쪽 위

 

4. 그래서 현재 방향으로 계속 가는 경우와 방향을 그 다음 순서의 방향으로 바꾸는 경우로 두번만 dfs를 돌리면 된다.

(단, 시작 위치에서는 무조건 방향이 오르쪽 아래로만 가야하기 때문에 dfs 실행 전에 지정해줬다.)

5. stack에는 다음 갈 위치와 지금까지 방문한 디저트 번호, 현재 방향이 담긴다.

 

dxy = [(1, 1), (1, -1), (-1, -1), (-1, 1)]
def dfs(x, y, nums, d):
    global i, j, ans
    stack = [(x, y, nums, d)]
    while stack:
        x, y, nums, d = stack.pop()

        for k in range(d, min(4, d + 2)):
            nx, ny = x + dxy[k][0], y + dxy[k][1]

            if -1 < nx < N and -1 < ny < N:
                if nx == i and ny == j:
                    ans = max(ans, len(nums))
                    continue

                if cafes[nx][ny] not in nums:
                    stack.append((nx, ny, nums + [cafes[nx][ny]], k))


T = int(input())
for tc in range(1, T + 1):
    N = int(input())
    cafes = [list(map(int, input().split())) for _ in range(N)]
    ans = -1
    for i in range(N - 1):
        for j in range(N - 1):
            if cafes[i][j] != cafes[i + 1][j + 1]:
                nums = [cafes[i][j], cafes[i + 1][j + 1]]
                dfs(i + 1, j + 1, nums, 0)

    print('#{} {}'.format(tc, ans))