1987. 알파벳
문제
- 시간 제한: 2초
- 메모리 제한: 256MB
Problem Analysis
최적의 경로를 선택할 수 있는 규칙은 따로 없고, 가능한 경우를 모두 조사하는 수밖에 없다. 현재까지의 경로를 함께 저장하며, 순회하면 된다.
이때, k 거리의 동일한 칸이라도 지나온 경로에 따라 다른 경우가 되기 때문에, BFS를 하면 Queue에 지수적으로 추가된다. 반면에, DFS는 거리만큼 stack에 쌓으면서 들어가므로, 메모리에 부담이 비교적 덜할 것으로 보인다.
Algorithm
DFS를 통해 문제를 해결한다.
인접 칸에 대하여,
- row, column의 범위
- 경로 중복 여부(bitmasking으로 각 알파벳의 방문 여부를 기록)
을 만족하면 다음 카운트로 recursive call.
return 값 중에서 최대를 선택
Data Structure
- board[r][c], 보드를 저장
- seqBits, 방문 여부를 bitmasking으로 체크
- count, DFS 깊이 체크
결과
Other
1 2 3
4 5 6
7 8 9
1 2 3
4 5 6
7 8 9
일반적으로 BFS를 1에서 시작하면, 1-2-5 순으로 5를 Queue에 넣은 후, 1-4-5로 접근할 때, 이미 방문한 5를 Queue에 추가하지 않는다. 그러나, 이 문제에서는 거리만 중요한 게 아니고, 경로의 차이를 고려해야 하기 때문에 5를 추가해야한다.
이처럼 Backtracking 문제에서는, BFS보다 DFS가 쉽고 직관적이다.
Author And Source
이 문제에 관하여(1987. 알파벳), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@smsh0722/1987.-알파벳저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)