dfs
-
[Lv.2] 게임 맵 최단거리Programmers/Level2 2022. 8. 30. 13:43
문제 ROR 게임은 두 팀으로 나누어서 진행하며, 상대 팀 진영을 먼저 파괴하면 이기는 게임입니다. 따라서, 각 팀은 상대 팀 진영에 최대한 빨리 도착하는 것이 유리합니다. 지금부터 당신은 한 팀의 팀원이 되어 게임을 진행하려고 합니다. 다음은 5 x 5 크기의 맵에, 당신의 캐릭터가 (행: 1, 열: 1) 위치에 있고, 상대 팀 진영은 (행: 5, 열: 5) 위치에 있는 경우의 예시입니다. 위 그림에서 검은색 부분은 벽으로 막혀있어 갈 수 없는 길이며, 흰색 부분은 갈 수 있는 길입니다. 캐릭터가 움직일 때는 동, 서, 남, 북 방향으로 한 칸씩 이동하며, 게임 맵을 벗어난 길은 갈 수 없습니다. 아래 예시는 캐릭터가 상대 팀 진영으로 가는 두 가지 방법을 나타내고 있습니다. 첫 번째 방법은 11개의 ..
-
[개념] BacktrackingAlgorithm/theory 2022. 8. 23. 21:55
Backtracking - 문제의 해결 방법을 탐색하다 가능성이 없다고 판단되는 후보를 즉시 가지치기(Pruning)하는 방식 - bfs 와 같은 방식으로 탐색하는 모든 방법으로, bfs는 backtracking의 골격을 이루는 알고리즘 - bfs 와 같은 재귀 방식으로 구현 - 운이 좋으면 시행착오를 거치지 않고 해답을 얻을 수 있지만, 최악의 경우 모든 경로를 거쳐야 함 - backtracking 에서 사용되는 가지치기(Pruning) 는 트리의 탐색 최적화 문제(제약 충족 문제(constraint satifaction problems))와도 연관 * 제약 충족 문제 : 수많은 제약 조건(constraint)을 충족하는 상태(States)를 찾아내는 수학 문제 : ex) 스토쿠, 8퀸 문제, 4색 문..