Recently, the distributed fiber optic sensing (DFOS) techniques have advanced rapidly. There emerges various types of DFOS sensors that can monitor physical parameters such as temperature, strain, and vibration. With these DFOS sensors deployed, the telecom networks are capable of offering additional services beyond communications, such as monitoring road traffic condition, monitoring utility pole health, monitoring city noise and accident, thus evolving to a new paradigm of Infrastructure-as-a-Sensor (IaaSr) or Network-as-a-Sensor (NaaSr). When telecom network carriers upgrade their infrastructures with DFOS sensors to provide such IaaSr/NaaSr services, there will arise a series of critical challenges: (1) where to place the DFOS sensors, and (2) how to provision the DFOS sensing fiber routes to cover the whole network infrastructures with the minimum number of DFOS sensors? We name this as the DFOS placement problem. In this paper, we prove that the DFOS placement problem is an NP-hard problem, and we analyze the upper bound of the number of DFOS sensors used. To facilitate the optimal solution, we formulate the DFOS placement problem with an Integer Linear Programming model that aims at minimizing the number of DFOS sensors used. Furthermore, we propose a cost-efficient heuristic solution, called Explore-and-Pick (EnP), which can achieve a close-to-optimal performance in a fast manner. We analyze the approximation ratio and the computational complexity of the proposed EnP algorithm. In addition, we conduct comprehensive simulations to evaluate the performance of the proposed solutions. Simulation results show that the EnP algorithm can outperform the baseline algorithm by 16% in average and 26% at best, and it achieves a performance that is close to the optimal result obtained by ILP.