BOJ 1987
-
[백준-1987]-[DFS-백트래킹]-알파벳알고리즘/백트래킹 2018. 11. 23. 02:38
문제링크 : https://www.acmicpc.net/problem/1987 이문제를 어떻게 접근할까 하다가 간단하겠지 하고 BFS로 풀었는데 절대 BFS풀면 안된다더라..그 이유는 동시에 같은 레벨의 다른 접점을 접근하기 때문에 만약 2레벨의 같은 알파벳이 있으면 방문 여부를 파악하기가 힘들다. 백트래킹으로 가능한 모든 방향을 접근하고 지나간 최대 칸수를 출력해주면 된다. 말이 쉽지 참 힘들었다. 예제는 항상 답이 나오는데 제출을 하면 항상 문제였다. 내가 푼 문제에 반례가 어떤게 있을까 하다가 스스로 예제를 만들어 보았다. 이것만 통과하면 제출해도 정답이 나올거 같다.. 내가 생각해낸 예제는 아래 표다. A B B C EC E D FG D H 만약 단순한 DFS만으로 결과를 도출해낸다면 최대 길이는..