미로 만드는 모듈을 C++로 만들어보았다.

총 3가지 형태의 미로에 대해 구현했다.

1. 외곽선이 없는 블럭 미로

h * w 만큼의 미로가 생긴다.

시작지점과 끝지점의 위치는

미로 내부 어느 곳이든 가능하다

2. 외곽선이 있는 블럭 미로

미로의 외곽선을 포함해서 (h+2)*(w+2) 크기의 미로가 생성된다.

시작지점과 끝지점은 이 외곽선 상에 위치한다.

이 두 지점을 제외하고는, 외각선은 항상 벽으로 막혀있다.

3. 벽 형태의 미로

(2*h+1)*(2*w+1) 크기의 미로가 만들어진다.

인덱스 i,j 좌표가 모두 홀수인 점들은 항상 길이고

모두 짝수인 점들은 항상 벽이다.

둘 중 하나만 홀수인 점은 "벽"으로,

이 지점의 값이 벽이거나 길이거나에 따라 미로를 생성한다.

간단히 예를 들면 아래와 같다.

붉은색 부분은 벽, 하얀 부분을 길이라고 보면

왼쪽처럼 되있는 (2*4+1)*(2*6+1) 의 배열을 이용해서

오른쪽과 같은 미로를 만들 수 있다.

알고리즘은 bfs를 응용해서 만들었다.

보통의 2차원 좌표계에서의 bfs는 queue에 점 좌표를 집어넣고

먼저 집어넣어진 좌표부터 순서대로 pop 해, pop된 좌표점을 기준으로 탐색을 돌린다.

이 코드에서는 pop을 할 때

집어넣어진 순서대로가 아닌, 랜덤한 순서의 좌표를 pop하고

그 좌표 주변으로 탐색시켰다.

탐색된 적이 없는 좌표를 발견하면.. queue에 집어넣고,

한번이라도 pop된 좌표를 발견하면 무시한다.

이미 queue 배열에 들어가있는 좌표를 발견했다면

무시하는 것이 아니라, 그 좌표의 path 좌표를

현재 기준이 된 좌표로 변경시키는 작업을 수행했다.

이렇게 하니 랜덤성이 조금 더 증가하는 기분이 들었다. 근거는 없다.ㅋ

시간복잡도는 O(h*w*수행횟수) 이다.

미로의 경로 길이의 최소값을 지정해줄 수 있는데,

만약 이 조건을 만족하는 미로를 생성하는데 실패했다면 

미로를 처음부터 다시 만들기 때문에.

수행 횟수도 시간복잡도에 들어간다.

소스코드는 아래 첨부한다.

bj_mang.cpp

파일이름은 바꾸기 귀찮다...

먼저 가로, 세로, 미로타입 등을 정해주고

.bind();를 해주고 (여기서 미로의 크기가 결정됨)

.generate();를 해서 미로를 생성한다. 그러면

std::vector<int> map; 에 미로 정보가 저장된다.

트리형태의 미로밖에 못만들지만,

그래서 루프 형태가 있는 미로는 못만들지만...

뭐 그정도는...

이 소스코드를 읽을 수 있는 수준이면 

다들 알아서 추가할 수 있잖아요?ㅋㅋㅋㅋ

여담으로, 미로의 가로,세로 크기는 3x3 초과하는 것을 권장합니다.

왜냐하면 지금은 시작점과 끝점 사이의 거리가 2 이상일 때만 미로를 만들기 때문이죠