백트랙킹
-
[백준 BOJ/C++] 1987 알파벳알고리즘, 코딩테스트/알고리즘 문제풀이 2023. 8. 16. 01:33
1987번: 알파벳 백트랙킹, DFS를 연습하기 적당한 문제다. 요구사항이 복잡하거나 구현량이 많지 않고 중복된 알파벳을 피해서 가장 멀리 갈 수 있는 경로를 찾아야 한다. 알파벳으로 채워진 맵에서 같은 알파벳을 중복하지 않게 방문하여 갈 수 있는 최대 거리를 구하는 문제다. 시작점은 항상 (0, 0) 이며 상하좌우 한 칸 씩 탐색해 나가면 된다. 몇 몇 실수하기 쉬운 부분이 있는지 정답 비율이 낮은 편이지만 복잡한 문제는 아니라서 백트랙킹, DFS 문제와 관련해 기본기를 쌓기 좋은 문제다. 문제의 포인트 백트랙킹 알고리즘 알파벳의 중복 피하기 백트랙킹 알고리즘 일반적으로 맵 형태의 입력이 주어지고 이동시켜가는 문제는 BFS든 DFS든 탐색 알고리즘을 이용해야하는 경우가 많다. 최단 경로를 찾아야 하는 ..