🍨 제목은 귀엽지만 풀이과정은 사악했던 디저트 카페 문제를 데려왔다.
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5VwAr6APYDFAWu
dfs 라는 것은 알겠는데 도저히 생각나지 않아서 약간 검색의 힘을 빌렸다.
1. 문제의 특징
이동할 수 있는 방향의 순서가 정해져 있다. 직사각형을 이루려면 시계방향 혹은 반시계방향으로 돌면서 탐색이 이뤄저야 한다. 지금 내가 갈 수 있는 방향은 이전의 방향, 그리고 시계방향으로 돌아간 방향 2가지로 제한되어있다는 뜻이다.
⇒ 함수의 인자에 방향을 나타내는(d)를 추가하여 기존에 오고 있는 방향으로 이동할 수 있다면 이동하고, 그렇지 않다면 그 다음 방향으로 탐색하는 코드를 추가했다.
2. 문제의 특징
한 번 방문한 곳을 재방문해도 안된다는 것은 dfs, bfs의 기본이지만,
이 문제의 특이한 점은 디저트의 종류도 달라야 한다 는 것이었다. 따라서 visited 배열 없이 디저트의 종류만 가지고도 문제를 풀이 할 수 있다.
나는 디저트를 먹으면 디저트 종류에 1을 check 하는 방식으로 총 먹은 디저트 수를 세었지만, 빈 배열에 먹은 디저트 종류를 append 하여, 배열 안에 dessert가 있는 지를 확인하는 방식으로 진행해도 된다.
di = [1, 1, -1, -1]
dj = [-1, 1, 1, -1]
def des(i, j, d): # i,j는 시작하는 좌표의 행,열 d는 방향이다.
global max_V
if d < 3:
tmp = d + 2
else:
tmp = d + 1
for k in range(d, tmp): # 현재 오는 방향, 그 다음방향으로 2가지 선택지가 있다
ni, nj = i + di[k], j + dj[k]
if si == ni and sj == nj: # 처음 시작점으로 돌아오는 경우, max값 갱신
max_V = max(sum(dessert), max_V)
return
if 0 <= ni < N and 0 <= nj < N :
if not dessert[arr[ni][nj]]: # 이전에 먹은 디저트가 아니라면,
dessert[arr[ni][nj]] = 1
des(ni, nj, k)
dessert[arr[ni][nj]] = 0
T = int(input())
for tc in range(1, T+1):
N = int(input())
arr = [list(map(int, input().split())) for _ in range(N)]
visited = [[0]*N for _ in range(N)]
max_V = -1
# 탐색을 시작 할 좌표 선택
for i in range(N - 2):
for j in range(1, N - 1):
si, sj = i, j
dessert = [0]*101
dessert[arr[si][sj]] = 1
des(si, sj, 0)
print(f"#{tc} {max_V}")
Uploaded by N2T