미로찾기 알고리즘 해결 전략 및 구현 (feat. DFS, BFS)

const offset = [ [0, 1], // 상 [0, -1], // 하 [-1, 0] // 좌 [1, 0] // 우 ] void find_path(maps, visited, pos) { if (pos == [4, 4]) // 종료 조건 return ; else { visited[pos] = true; // 현재 위치를 방문한 것으로 표시 stack.push(pos); // 현재 위치를 스택에 넣기 for (i = 0; i < 4; i++) // 상하좌우 이동 여부 탐색 { next = pos + offset[i]; // 다음 좌표 저장 if (is_movable(maps, next) // 이동 가능 여부 판단 find_path(maps, visited, next); // 다음 경로로 이동 } stack.pop(pos); // 탐색에 실패하면 스택에서 현재 위치 제거 } }

[0, 0] -> 시작 지점 [0, 1] [0, 2] [0, 3] [1, 3] [2, 3] -> 분기 지점 [2, 2] -> 위로 이동 [2, 1] [2, 0] [3, 0] [4, 0] -> 벽에 부딪히는 순간 뒤로 이동 [3, 0] [2, 0] [2, 1] [2, 2] [2, 3] -> 분기 지점 [3, 3] -> 오른쪽으로 이동 [4, 3] [4, 4] -> 종료 지점

// 변수 선언 int NUM_DIRECTIONS = 4; static int DIRECTION_OFFSETS[NUM_DIRECTIONS][2] = { {0, -1}, // 0 (상) {1, 0}, // 1 (우) {0, 1}, // 2 (하) {-1, 0} // 3 (좌) }; struct MapPositionType { int x; int y; int direction; } MapPosition; enum PosStatus { NOT_VISIT = 0, WALL = 1 , VISIT = 2 }; // 재귀 함수 int findPath(int maze[HEIGHT][WIDTH], MapPosition pos, LinkedStack *pStack) { MapPosition nextPos; int nextX; int nextY; if (!pStack) return (ERROR); // 현재 위치가 미로의 범위를 벗어나는 지 확인 if (pos.x < 0 || pos.y < 0 || pos.x >= WIDTH || pos.y >= HEIGHT) return (FALSE); // 현재 위치가 벽이거나 이미 방문한 곳인지 확인 else if (maze[pos.y][pos.x] == WALL || maze[pos.y][pos.x] == VISIT) return (FALSE); // 도착 지점에 도달한 경우 else if (maze[pos.y][pos.x] == END) { pushLS(pStack, pos); return (TRUE); } // 백트래킹을 통한 탐색 반복 else { pushLS(pStack, pos); // 현재 위치를 스택에 저장 maze[pos.y][pos.x] = VISIT; // 현재 위치를 2로 변경 while (pos.direction < NUM_DIRECTIONS) { // 다음 좌표 설정 nextX = pos.x + DIRECTION_OFFSETS[pos.direction][0]; nextY = pos.y + DIRECTION_OFFSETS[pos.direction][1]; nextPos.x = nextX; nextPos.y = nextY; nextPos.direction = 0; if (findPath(maze, nextPos, pStack)) return (TRUE); pos.direction += 1; } // 길을 찾지 못하면 스택에서 현재 위치 제거 popLS(pStack); return (FALSE); } }

void bfs(maps, start, visited) { queue.enqueue([start]); // 시작 지점을 큐에 넣기 while (!queue.isEmpty()) // 큐가 비워지기 전까지 반복 { now = queue.dequeue(); // 큐에서 꺼내기 if (now == [end]) // 종료 지점에 도달한 경우 return ; visited[now] = true; // 현재 위치를 방문 처리 for (int i = 0; i < 4; i++) { next = now + offset[i]; // 다음 방문 좌표 생성 if (is_movable(maps, next, visited)) // 이동 가능 여부 확인 queue.enqueue(next); // 큐에 다음 방문 좌표 넣기 } } }

// 변수 선언은 이전 예제와 동일 int is_movable(int maze[HEIGHT][WIDHT], int visited[HEIGTH][WIDTH], MapPosition pos) { // 현재 위치가 미로의 범위를 벗어나는 지 확인 if (pos.x < 0 || pos.y < 0 || pos.x >= WIDTH || pos.y >= HEIGHT) return (FALSE); // 현재 위치가 벽이거나 이미 방문한 곳인지 확인 if (maze[pos.y][pos.x] == WALL || maze[pos.y][pos.x] == VISIT) return (FALSE); return (TRUE); } // BFS int findPath(int maze[HEIGHT][WIDTH], int visited[HEIGHT][WIDTH], MapPosition pos) { LinkedQueue queue; MapPosition currPos; MapPosition nextPos; int nextX; int nextY; queue.enqueue(pos); // 처음 시작 위치를 큐에 넣기 while (!queue.isEmpty()) { currPos = queue.dequeue(); // 큐에서 꺼내기 if (maze[currPos.y][currPos.x] == END) // 도착 지점에 도달한 경우 return (maze[currPos.y][currPos.x]); if (visited[currPos.y][currPos.x] == VISIT) // 현재 위치를 방문했는지 확인 continue ; visited[currPos.y][currPos.x] = VISIT; // 현재 위치를 VISIT 으로 변경 while (currPos.direction < NUM_DIRECTIONS) { // 다음 좌표 설정 nextX = currPos.x + DIRECTION_OFFSETS[currPos.direction][0]; nextY = currPos.y + DIRECTION_OFFSETS[currPos.direction][1]; nextPos.x = nextX; nextPos.y = nextY; nextPos.direction = 0; if (is_movable(maze, visited, nextPos) { // 다음 이동 지점에 이전 이동 거리 + 1 저장 maze[nextY][nextX] = maze[currPos.y][currPos.x] + 1; queue.enqueue(nextPos); // 다음 이동 지점 큐에 저장 } pos.direction += 1; } } }