You can download the stock firmware from Sammobile.com and reflash the phone. That followed by a factory reset (if it doesn't do a reset in the process - I'm not a Samsung expert) will remove anything from the phone because it completely overwrites the system.
As for not getting back in, without knowing how they got in in the first place that's impossible to say. It is not easy to get into the root of an up-to-date S9 in the first place. But the two most likely routes for any infection are either through a trojan (i.e. you installed an app that contains hidden malware - unlikely if you only install from the Play Store, highly likely if you download "free" copies of paid apps from the web) or that your Google or Samsung account has been compromised. So I would suggest taking steps to secure both of those (change passwords, enable two-factor authentication if you haven't already done so, check what devices have been used to access them, de-authorise any you aren't 100% sure are secure, etc). But don't do this from a compromised phone, and don't reconnect a cleaned phone to these accounts until you are sure they are secured.
When you say "the files go all the way to the root directory" can you see them, or is this an assumption or inference? If you can see things that you cannot remove what are they? This might help someone identify the cause (though in fairness I must also say that we get many people reporting that they've discovered something suspicious which is in fact completely normal, so I have to reserve judgement until we know more).