Pues para discriminar las ciudades distintas, debes también agrupar por las ciudades. DE lo contrario no las diferenciará.
Esto suponiendo que en el empleado tienes un campo ciudad_id, o como sea qu elo identifiques.
Nota: Si cada iddep es único, agrupar por el nombre del departamento es innecesario y superfluo.
Nota 2: No uses "*" para las consultas, especialmente con JOIN. Indica los campos que realmente vas a usar, así te evitas traer columnas repetidas y datos basura (datos que no se usarán en ese proceso).