문제

• 
• 시간 제한: 2초
• 메모리 제한: 256MB

Problem Analysis

최적의 경로를 선택할 수 있는 규칙은 따로 없고, 가능한 경우를 모두 조사하는 수밖에 없다. 현재까지의 경로를 함께 저장하며, 순회하면 된다.
이때, k 거리의 동일한 칸이라도 지나온 경로에 따라 다른 경우가 되기 때문에, BFS를 하면 Queue에 지수적으로 추가된다. 반면에, DFS는 거리만큼 stack에 쌓으면서 들어가므로, 메모리에 부담이 비교적 덜할 것으로 보인다.

Algorithm

DFS를 통해 문제를 해결한다.

인접 칸에 대하여,

• row, column의 범위
• 경로 중복 여부(bitmasking으로 각 알파벳의 방문 여부를 기록)

을 만족하면 다음 카운트로 recursive call.

return 값 중에서 최대를 선택

Data Structure

• board[r][c], 보드를 저장
• seqBits, 방문 여부를 bitmasking으로 체크
• count, DFS 깊이 체크

결과

Other

1 2 3
4 5 6
7 8 9

일반적으로 BFS를 1에서 시작하면, 1-2-5 순으로 5를 Queue에 넣은 후, 1-4-5로 접근할 때, 이미 방문한 5를 Queue에 추가하지 않는다. 그러나, 이 문제에서는 거리만 중요한 게 아니고, 경로의 차이를 고려해야 하기 때문에 5를 추가해야한다.

이처럼 Backtracking 문제에서는, BFS보다 DFS가 쉽고 직관적이다.