Section A:
A1) Sort all tiles into two tables: one table for boundary tiles (any tiles that touch empty space on one or more sides so they need the outline effect), and a second table with all "inner" tiles (any tiles that are completely surrounded by other tiles).
You can update these tables during the game, just keep them separate.
Then when drawing, section B:
B1) Draw all tiles in the "boundary tiles table" in 2 passes: one dilation/outline pass, and one standard pass.
B2) Draw all tiles in the "inner tiles table", so finish covering (hiding) any inside parts of the outlines.
This is similar to how you do a 3D outline effect on meshes: you draw the mesh in flat black and expanded by its normals, then draw the original mesh on top. Only the black outline will be visible, not the black inside.
(Image by Simon Schreibt)
This is the principle behind this, drawing the black expanded tile, then drawing it again but normal so only the outside parts of the black drawing are visible.
Edit: you only need all of this if your tiles don't have perfect square shapes, like a random outline with transparent pixels. If they are perfectly square then you can make the outlining much faster by just computing the boundaries of the empty space and draw the lines along that boundary. You go through every occupied cell in your tilemap and check the 4 sides around that cell (top, bottom, left, right): If any sides lead to an empty cell then add an outline dash at that side. At the end you'll have all outline dashes that you need to draw.