문제
- SWEA-2105 : [모의 SW 역량테스트] 디저트 카페
풀이-파이썬
기본적인 백트래킹 문제이다. 다만 진행 방향이 바뀔 경우, 기존에 진행하던 방향으로는 더 이상 진행하지 못하는 부분을 구현하는 게 키포인트였다.
stack = []
his = set([])
def isSafe(i, j):
if -1<i<M and -1<j<M:
if arr[i][j] in stack:
return 0
if visit[i][j] == 0:
return 1
return 0
def search(a, b, prev):
global maxi
if [a,b]==start and 3<len(stack):
maxi = max(maxi, len(stack))
return
# 방향
dirs = [ [1,1], [-1,1], [-1,-1], [1,-1] ]
# 방향을 틀면 기존에 가던 방향으로는 못간다
for i, j in dirs:
if (i,j) not in his:
X = a+i
Y = b+j
if isSafe(X,Y):
visit[X][Y] = 1
stack.append(arr[X][Y])
if prev != (i,j):
his.add(prev)
search(X,Y, (i,j))
his.remove(prev)
else:
search(X,Y, prev)
visit[X][Y] = 0
stack.pop()
T = int(input())
for test_case in range(1, T + 1):
maxi = 0
M = int(input())
arr = []
for i in range(M):
arr.append(list(map(int, input().split())))
visit = [ [0]*M for _ in range(M) ]
# 출발점
for a in range(M):
for b in range(M):
start = [a,b]
search(a, b, (1,1))
if maxi == 0:
maxi = -1
print("#%d %d" %(test_case, maxi))