[BOJ1987] 알파벳

말이 최대한 몇 칸을 지날 수 있는지

• 세로 가로, R C 표
• 각 칸에 대문자 알파벳 하나씩
• 1행 1열에는 말이 놓여있음
• 말은 상하좌우로 인접한 네 칸 중 한 칸으로 이동
• 새로 이동한 칸은 지금까지 지나온 칸에 적혀있는 알파벳과는 달라야함
• 같은 알파벳이 적힌 칸을 두 번 지날 수 없음
• 좌측상단에서 시작해 말이 최대 몇 칸 지나는지, 좌측상단 칸도 포함

입력

• R, C (1<= R, C <=20)
• R개 줄에 걸쳐 보드에 적혀있는 C개의 대문자 알파벳

출력

• 첫째 줄에 말이 지날 수 있는 최대의 칸 수 출력

설계

• DFS를 이용해 지나온 칸을 다 저장면서 다음에 탐색될 칸은 지나온 칸이 아닌 알파벳이면 카운팅

피드백

• 알파벳을 저장하고 비교하는 부분의 아이디어가 잘 안 떠올랐음
• 알파벳 저장 -> dfs 재귀 -> 알파벳 꺼내기 (제일 중요)
• 위의 작업을 vector를 이용하였더니 시간초과가 계속 났다.
• 단순 배열을 이용 : 알파벳 26자, 해당 알파벳을 지나면 +1 (true)

How I solved(click to github)

---

ref :
BOJ1987