백준 1987번 알파벳 C++

 

1. 문제 설명

세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다.

보드의 각 칸에는  대문자 알파벳이 하나씩 적혀 있고, 0,0칸에는 말이 놓여있다.

말은 상하좌우로 인접한 네 칸 중 한칸으로 이동이 가능하다.

새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과 달라야 한다.

같은 알파벳이 적힌 칸을 두 번 지날 수 없다.

 

DFS 이용해서 겹치지않는 알파벳이 나올때 까지 탐색하며 count를 ++ 해주다가

겹치는 알파벳이 나오면 백트래킹 이용해서 여지껏 지났던 부분을 다 롤백해주고 다른 방향으로 찾아준다.