We propose a primary user-aware k-hop routing scheme that can be plugged into any cognitive radio network routing protocol to adapt, in real time, to the environmental changes. The main use of this scheme is to make the compromise required between the route overhead and its optimality based on a user-defined utility function. We analytically derive the optimal discovery radius (k) that achieves this target. Evaluations on NS2 show that our scheme can enhance the current routing protocols in terms of throughput with minimal overhead.