풀이
import sys; sys.stdin = open('input_디저트카페.txt', 'r')
dr = [1, 1, -1, -1]
dc = [1, -1, -1, 1]
def lets_go(answer, r, c, start, way):
global result
if (r, c) == start:
result = max(result, answer)
return
if r < 0 or c < 0 or r >= N or c >= N:
return
if visited[desert[r][c]]:
return
else:
visited[desert[r][c]] = 1
lets_go(answer + 1, r + dr[way], c + dc[way], start, way)
if way + 1 < 4:
lets_go(answer + 1, r + dr[way + 1], c + dc[way + 1], start, way + 1)
visited[desert[r][c]] = 0
for tc in range(int(input())):
N = int(input())
desert = [list(map(int, input().split())) for _ in range(N)]
visited = [0] * 102
result = -1
for i in range(N):
for j in range(N):
visited[desert[i][j]] = 1
lets_go(1, i + 1, j + 1, (i, j), 0)
visited[desert[i][j]] = 0
print(f'#{tc+1}', result)
간단한 해설
- 재귀의 개념의 기초가 탄탄해야 dfs의 재귀를 사용하여 풀 수 있다.
- dfs에 넣어줄 매개 변수를 잘 선택하고 활용해야 한다.
- 직접 코드를 디버깅 해보며 살펴볼 것을 추천한다.
