Faits:
A.
Depuis 1990, X._ a subi trois condamnations à des peines respectivement de six ans et demi, huit ans et sept ans, en particulier pour des infractions contre l'intégrité sexuelle. Il est actuellement soumis à une mesure institutionnelle (<ref-law>).
B.
Par décision du 3 juin 2012, l'Office d'application des peines et mesures du canton de Neuchâtel a refusé, en raison du risque de fuite et de récidive, la demande de X._ de pouvoir bénéficier d'une sortie accompagnée. Saisi d'un recours du prénommé, le Département de la Justice, de la sécurité et des finances du canton de Neuchâtel l'a rejeté par décision du 8 février 2013.
Par arrêt du 14 mai 2013, la Cour de droit public du Tribunal cantonal du canton de Neuchâtel a admis le recours de X._, a annulé les décisions des 3 juin 2012 et 8 février 2013 et renvoyé la cause pour nouvelle décision.
C.
Le Ministère public, parquet régional de la Chaux-de-Fonds, forme un recours en matière pénale au Tribunal fédéral contre cet arrêt, concluant à son annulation.

Considérant en droit:
1.
Le recours en matière pénale est ouvert contre les décisions sur l'exécution des peines et mesures (<ref-law>). Il doit s'agir d'une décision qui met fin à la procédure (décision finale, <ref-law>). En revanche, une décision incidente qui ne porte pas sur la compétence ou sur une demande de récusation ne peut faire l'objet d'un recours en matière pénale que si elle peut causer un préjudice irréparable (<ref-law>) ou si l'admission du recours peut conduire immédiatement à une décision finale qui permet d'éviter une procédure probatoire longue et coûteuse (let. b). Une décision de renvoi, comme l'arrêt attaqué, a un caractère incident. Elle ne cause en principe pas de dommage irréparable. La jurisprudence, qu'invoque le recourant, admet toutefois l'existence d'un préjudice irréparable lorsqu'une administration est obligée par une décision de l'autorité supérieure de statuer dans un sens qui lui paraît contraire au droit, en particulier lorsque la décision de renvoi est assortie d'injonctions très précises (<ref-ruling> consid. 1.2 p. 138).
En l'espèce, la cour cantonale a relevé que le refus pur et simple de sortie accompagnée ne pouvait pas être confirmé sans instruction complémentaire. Il fallait examiner si une sortie pouvait concrètement être organisée de manière à satisfaire aux exigences sécuritaires strictes recommandées par la commission de dangerosité et l'expert. Il y avait ainsi lieu de mener des investigations complémentaires auprès de l'établissement de résidence et de l'expert-psychiatre (cf. arrêt p. 9). Au vu de cette motivation, l'exception permettant un recours immédiat n'est pas réalisée. En effet, compte tenu de la palette assez large des vérifications à mener et de la formulation ouverte fixant le cadre du renvoi, la jurisprudence précitée n'est pas applicable. Il n'y a pas de préjudice irréparable en l'occurrence. Aucun motif d'économie de procédure ne justifie non plus d'appliquer l'<ref-law>. Il s'ensuit que le recours est irrecevable.
Le cas échéant, le recourant aura la faculté d'attaquer la décision incidente avec la décision finale si elle influence celle-ci (cf. <ref-law>). A noter que le recourant est la seule entité étatique habilitée à former un recours en matière pénale devant le Tribunal fédéral (cf. <ref-ruling> consid. 2.3 p. 53), ce qui implique qu'il puisse aussi être partie et recourir en instance cantonale (cf. <ref-law>), ce que prévoit d'ailleurs la législation cantonale (art. 102 al. 3 de la loi neuchâteloise sur l'exécution des peines privatives de liberté et des mesures pour les personnes adultes; RS/NE 351.0).
2.
Il est statué sans frais (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce:
1.
Le recours est irrecevable.
2.
Il est statué sans frais judiciaires.
3.
Le présent arrêt est communiqué aux parties et au Tribunal cantonal de la République et canton de Neuchâtel, Cour de droit public.
Lausanne, le 22 juillet 2013
Au nom de la Cour de droit pénal
du Tribunal fédéral suisse
Le Président: Mathys
La Greffière: Livet