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); // 탐색에 실패하면 스택에서 현재 위치 제거
	}
}

// 변수 선언
 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;
	      }
		}
}