We consider a 3D network construction problem in the post-disaster scenario, where large urban areas are communication-wise isolated from the outside environment due to the severely damaged network infrastructure. Our main goal is to reconnect the isolated regions with the outside environment using unmanned aerial vehicles (UAVs) by building 3D aerial ad-hoc networks. Prior to network construction, we aim to capture the global map information over region of interests (RoI) by exploring all obstacles in the unknown region. We propose an efficient technique for collaborative 3D terrestrial exploration using multiple UAVs based on our distributed path planning algorithm, which finds collision-free exploration paths. Then, we present an optimal full-coverage 3D aerial ad-hoc network construction by deploying the minimum number of UAVs to indispensable spots while obtaining maximum network coverage. Simulation results demonstrate that our proposed exploration scheme outperforms several counterpart algorithms in terms of traversal time and redundant visit rate. Also, our network construction algorithm guarantees almost full coverage toward terrestrial space with only minimal UAV usage.