[DFS, Backtracking] 백준 : 1987_알파벳

[inseonyun]

Source URL : https://www.acmicpc.net/problem/1987

문제 요구사항 :

• 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다.
• 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.
• 말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다.
• 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.
• 좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오.
• 말이 지나는 칸은 좌측 상단의 칸도 포함된다.
• 첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1 ≤ R,C ≤ 20)
• 둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다.
• 첫째 줄에 말이 지날 수 있는 최대의 칸 수를 출력한다.

접근 방법 :

• 문제 요구사항인 '새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. '를 만족시키기 위해, 알파벳(26개)의 visited 배열을 구성하고 해당 알파벳을 지나왔는지 check하며 dfs 탐색을 수행한다. 이때, dfs 수행한 해당 루트가 최대 이동 경로가 아닐 수 있으므로, 백트래킹을 하며 탐색하도록 한다.

풀이 순서 :

1. R, C와 맵 정보를 입력 받는다.
2. 맵의 첫 시작 좌표 ( 0, 0) -> visited [ map [0][0] - 'A']의 값을 true로 하고, dfs에 0, 0, 1(cost) 를 넣고 탐색한다.
3. DFS 수행
   • res(초기값 0)의 값이 cost보다 작다면, res에 cost 값을 넣는다.
   • 상,하,좌,우 깊이 우선 탐색을 진행하며, 탐색 전, visited[ map [nx][ny] -'A']값에 true를 넣고,
   • 탐색이 종료된 후 백트래킹을 위해 다시 해당 인덱스 값에 false를 넣는다.
   • 이와 같은 작업 반복
4. res 출력

[inseonyun]

문제 풀이 결과 :