(JAVA) 백준 1987번 : 알파벳 -- [DFS]

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

1987번: 알파벳

 

이 문제는 DFS 문제입니다.

 

BFS를 사용하면 모든 경우(상하좌우 및 모든 경로)에 대해 분기처리되서 하나씩 비교해야하기때문에 아닌것 같고

DFS를 사용해서 맞는 경우에만 깊이있게 최대 경로를 탐색해내는게 맞는 것 같아서 DFS를 사용했습니다.

 

알고리즘은 간단해서,

 

  - 1행 1열부터 말 움직이기 시작.
  - 별도 목적지가 없고, 최대로 움직일 수 있는 칸을 구하는 문제기 때문에 DFS(맨 첫 번째칸도 지나간 칸) = 초기값 1
  - R,C(즉, x와 y는 <= 20)
  - 이전까지 지나온 칸에 적힌 알파벳이면 이동 불가능 -> 지금까지 지나온 알파벳 모두 저장 -> boolean 배열로 알파벳 대문자(A ~ Z) 까지를 인덱스로 해서 사용하면 True, 사용하지 않으면 False로 만들어보자.

 

이고,

 

핵심은

 

  1) 지나온 경로에 사용한 알파벳 체크 -> boolean[26], 인덱스 : 해당 지점의 알파벳 - 'A'

  2) DFS 재귀함수 호출 전 알파벳 사용(True), 호출 후 알파벳 미사용 변경(False)

  

인데, 효율성이 높진 않더라구요..

이런 알고리즘으로는 효율적이지만, 다른 정답자의 풀이법을 보니 비트마스킹 활용하는 것 같은데 제가 풀지 않아서 차마 비트마스킹으로 문제풀이 리뷰글을 적을 수 없었습니다..

 

 

 

감사합니다.

 

소스코드

---