In this paper, we consider an aerial ad-hoc network construction problem using UAVs in a disaster scenario. We aim to reconnect the communication-wise isolated urban area with the outside communication infrastructure. Our main goal is to perform both network exploration and relay deployment tasks at the same time by taking a progressive optimization toward a self-organizing network construction. We propose a novel UAV exploration-and-deployment algorithm that gradually explores the region of interests and achieves full network coverage in a fast manner. Then, we present an effective network refinement algorithm based on clustering that minimizes the number of UAVs for deployment by finding out essential UAVs, while keeping the similar network coverage performance. Simulation results demonstrate that our proposed scheme significantly reduces the execution time for network exploration and deployment compared to a baseline counterpart. Also, our cluster-based network refinement algorithm provides a very lightweight yet effective solution, well-balancing between UAV resource and computation overhead.