This paper presents an online coverage method for the exploration of unknown oceanic terrains using multiple autonomous underwater vehicles (AUVs). Working from the concept of planar algorithm developed by Hert, this study attempts to develop an improved method. Instead of theoretical research, it focuses on the practical aspects of exploration by considering the equations of motion for AUVs that are actually used in oceanic exploration as well as on the characteristics of complex oceanic topography and other realistic variables, such as sea current. These elements are used to calculate cross track error (CTE) and path width for AUV movement. The validity of the improved algorithm for terrain coverage is first verified mathematically and then by a simulation of the real underwater environment that analyzes the path length and time taken for the coverage as well as the missed areas, which is the key element of efficiency. In order to apply the improved method to the multi-AUV operation, each AUV was assigned a covering or a scanning role by means of a dynamic role-changing mechanism. The results showed that the multi-AUV operation has an advantage over a single-AUV operation in many ways. The method proposed in this study will be useful not only for commercial applications but also for mine counter-measures (MCMs) and rapid environmental assessments (REAs) as part of naval military operations as well. We also believe that it will be ideal for use in variable oceanic environment, particularly in shallow water terrains. For the purposes of this study, we assume that the communication between AUVs is problem-free.