[김진영_]

1. 다음의 조건을 만족하는 미로를 받으셔야 점수를 받으실 수 있습니다.

문제에 명시되어 있는 미로의 정의:
(a) 입구와 출구가 맨 윗줄의 방과 맨 아랫줄의 방에 각각 하나이고
(b) 입구에서 출구까지의 통로가 유일해야 합니다.
특히 유일하다는 조건에 주의해서 만들어 주세요.

이 조건은 반드시 지켜 주셔야 하는 조건입니다. 이 조건만 만족하더라도 상당한 기본 점수를 받으실 수 있습니다.



2. 미로의 목표는 문제에도 나와 있지만, 될 수 있으면 어렵게 만들자는 것입니다. 이는 다소 주관적일 수도 있으나, 문제에 명시되어 있는 만큼 어느 정도 차등을 두어 채점하려고 합니다.

아래의 조건을 만족할수록 복잡한 미로로 봅니다. 혹시 다르게 생각하신다면 이 글에 답글로 달아 주시면 고려해 보겠습니다.

(a) 입구에서 도달가능한 방이 많을수록 복잡한 미로로 봅니다. 미로에 입구에서 도달이 불가능한 방이 있다면 의미가 없겠죠. 가장 좋은 경우는 n*m개의 방이 모두 입구에서 도달 가능한 경우입니다.

(b) 임의성이 있을수록 복잡한 미로로 봅니다. 문제네 명시된 것처럼 적당히 혼동스러운 모습을 띄려면 random함수를 이용해 임의적인 미로를 만드시는 것이 좋습니다. 만일 여러분이 만드신 함수를 이용해 만든 두 미로 (mazeGen 10 10)과 (mazeGen 20 20)가 크기만 커졌을 뿐인 유사한 형태의 미로를 돌려준다면, 복잡한 미로 생성기로 보기 곤란합니다.

(c) 어려운 미로를 단순하게 생각해 보면 첫째, 입구에서 출구까지의 거리가 길고, 둘째, 입구에서 출구까지 가는 길까지 갈림길이 많아야 할 것입니다. 하지만 생각해 보시면 알겠지만 이 둘은 서로 trade-off가 있습니다. 하나의 조건을 만족하려 하다 보면 다른 하나의 조건이 무시되게 됩니다. 가장 쉽게 생각해서 입구에서 출구까지의 거리가 가장 긴 미로를 만들면 갈림길이 하나도 없는 미로가 될 것입니다. 이 미로를 복잡한 미로라고 보기는 힘들겠죠. 이 두 조건 사이에 적절한 균형을 맞춰 주실수록 복잡한 미로라고 볼 수 있을 것입니다. (b)를 만족하면 거의 자동적으로 이 조건도 만족할 것입니다.

[김태훈]

미로를 랜덤으로 구현할 때 랜덤이 어떻게 돌아가느냐에 따라(즉 운에 따라) 미로의 목표를 훌륭하게 달성하느냐 허접하게 달성하느냐가 많이 차이날 수도 있는 소스의 경우 점수 채점이 어떻게 되나요?

[김진영_]

쉽게 생각할 수 있는 방법으로는 랜덤으로 여러 번 미로를 만들어 보신 뒤 가장 좋은 미로를 돌려주는 방법이 있겠습니다.

[김현우]

여러 번 미로를 만들어서 가장 복잡한 미로를 돌려주는 방식으로 사용해도 운이 나쁠 경우 그 여러 번 만든 미로 모두 충분히 복잡하지 않을 가능성도 있기 때문에

미로생성함수가 적당히 복잡한 미로를 뱉어낼 때까지 반복호출하는 방법을 써야 출력된 미로의 복잡성을 보장받을 수 있을 것 같습니다.

그리고 이 경우에 복잡한 미로의 기준을 높게 잡을수록 mazeGen의 수행시간도 그에 따라 늘어나게 됩니다

수행시간의 대략적인 마지노선을 설정해주시면 기준을 설정하는 데 많은 도움이 될 것 같습니다.

[김진영_]

크기는 말씀드렸듯 30 by 30을 넘지 않을 것이고, 시간은 한 번 mazeGen 함수를 수행할 때마다 1~2분을 넘어가지 않게 해 주세요.

이 부분에 대해 너무 걱정하지는 마시기 바랍니다. 물론 지나치게 랜덤성에 의존하시면 안 되겠지만.. 실행은 여러 가지 크기에 대해 채점해 보게 될 텐데, 이 중에서 운이 나빠 몇 번 정도 복잡하지 않은 미로가 나왔다고 해도 전체적으로 일정 수준 이상이라면 문제삼지 않겠습니다.