프로그래머스 - 미로 탈출

문제 링크

첫 제출(실패)

using System;
using System.Collections.Generic;

public class Solution {
    public int solution(string[] maps)
    {
        (int x, int y) s = (-1, -1);
        (int x, int y) l = (-1, -1);
        (int x, int y) e = (-1, -1);
           
        for (var i = 0; i < maps.Length; i++)
        {
            for (var j = 0; j < maps[i].Length; j++)
            {
                switch (maps[i][j])
                {
                    case 'S': s = (i, j); break;
                    case 'L': l = (i, j); break;
                    case 'E': e = (i, j); break;
                }
            }
        }

        var toLever = Calc(maps, s, l);
        if (toLever == -1) return -1;
        var toExit = Calc(maps, l, e);
        if  (toExit == -1) return -1;
        return toLever + toExit;
    }

    private int Calc(string[] maps, (int x, int y) from, (int x, int y) to)
    {
        (int x, int y) size = (maps.Length, maps[0].Length);
        var nexts = new PriorityQueue<(int x, int y), int>();
        nexts.Enqueue(from, Manhattan(from, to));
        
        var visited = new bool[size.x, size.y];
        var dists = new int[size.x, size.y];

        while (nexts.Count > 0)
        {
            var now = nexts.Dequeue();
            visited[now.x, now.y] = true;
            if (now == to) return dists[now.x, now.y];

            var currentDist = dists[now.x, now.y];
            var candidates = new[]
            {
                (now.x - 1, now.y),
                (now.x + 1, now.y),
                (now.x, now.y - 1),
                (now.x, now.y + 1)
            };

            foreach (var (x,y) in candidates)
            {
                if (x < 0 || x >= size.x || 
                    y < 0 || y >= size.y || 
                    visited[x, y] ||
                    maps[x][y] == 'X') continue;

                dists[x, y] = currentDist + 1;
                var priority = dists[x, y] + Manhattan((x, y), to);
                nexts.Enqueue((x, y), priority);
            }
        }
        
        return -1;
    }

    private int Manhattan((int x, int y) from, (int x, int y) to)
    {
        return Math.Abs(from.x - to.x) + Math.Abs(from.y - to.y);
    }
}

A* 알고리즘으로 해결하려고 했는데, 단순히 알고리즘을 잘못 구현해서 실패했다. A* 알고리즘은 같은 위치를 한 번 방문한다고 끝나면 안되고, 더 짧은 경로가 발견되면 갱신해주어야 한다.

사실 이 문제는 굳이 최단 경로 알고리즘을 사용할 필요는 없었다. 가중치가 없기 때문에, 단순히 시작 지점을 기준으로 BFS 트리를 만들어주면 모든 칸까지의 최단 경로 트리가 완성이 된다.

수정된 코드(통과)

using System;
using System.Collections.Generic;

public class Solution {
    public int solution(string[] maps)
    {
        (int x, int y) s = (-1, -1);
        (int x, int y) l = (-1, -1);
        (int x, int y) e = (-1, -1);
           
        for (var i = 0; i < maps.Length; i++)
        {
            for (var j = 0; j < maps[i].Length; j++)
            {
                switch (maps[i][j])
                {
                    case 'S': s = (i, j); break;
                    case 'L': l = (i, j); break;
                    case 'E': e = (i, j); break;
                }
            }
        }

        var toLever = Calc(maps, s, l);
        if (toLever == -1) return -1;
        var toExit = Calc(maps, l, e);
        if  (toExit == -1) return -1;
        return toLever + toExit;
    }

    private int Calc(string[] maps, (int x, int y) from, (int x, int y) to)
    {
        (int x, int y) size = (maps.Length, maps[0].Length);
        var nexts = new Queue<(int x, int y)>();
        var visited = new bool[size.x, size.y];
        var dists = new int[size.x, size.y];

        nexts.Enqueue(from);
        visited[from.x, from.y] = true;

        while (nexts.Count > 0)
        {
            var now = nexts.Dequeue();
            if (now == to) return dists[now.x, now.y];

            var candidates = new[]
            {
                (now.x - 1, now.y),
                (now.x + 1, now.y),
                (now.x, now.y - 1),
                (now.x, now.y + 1)
            };

            foreach (var (x, y) in candidates)
            {
                if (x < 0 || x >= size.x || 
                    y < 0 || y >= size.y || 
                    visited[x, y] || 
                    maps[x][y] == 'X') continue;

                visited[x, y] = true;
                dists[x, y] = dists[now.x, now.y] + 1;
                nexts.Enqueue((x, y));
            }
        }
    
        return -1;
    }
}

물론, A* 알고리즘도 올바르게 쓰면 통과할 수 있다. 더 이상 방문 기록은 없고, 대신 처음에는 거리가 무한(여기선 int를 사용하니 int.MaxValue로 대체)한 것으로 초기화하고, 더 짧은 경로가 나타날때마다 갱신해주는 방식을 써야 한다.

아래 코드로도 통과는 했지만, BFS보다 수행 시간이 오래 걸렸다. 알고리즘 자체가 더 무겁기 때문에 당연한 결과. 핵심적인 원인은 우선순위 큐가 단순 큐보다 삽입/삭제 복잡도가 높다는 것이다.

올바른 A* 알고리즘 코드

using System;
using System.Collections.Generic;

public class Solution {
    public int solution(string[] maps)
    {
        (int x, int y) s = (-1, -1);
        (int x, int y) l = (-1, -1);
        (int x, int y) e = (-1, -1);
            
        for (var i = 0; i < maps.Length; i++)
        {
            for (var j = 0; j < maps[i].Length; j++)
            {
                switch (maps[i][j])
                {
                    case 'S': s = (i, j); break;
                    case 'L': l = (i, j); break;
                    case 'E': e = (i, j); break;
                }
            }
        }

        var toLever = Calc(maps, s, l);
        if (toLever == -1) return -1;
        var toExit = Calc(maps, l, e);
        if (toExit == -1) return -1;

        return toLever + toExit;
    }

    private int Calc(string[] maps, (int x, int y) from, (int x, int y) to)
    {
        (int x, int y) size = (maps.Length, maps[0].Length);
        
        var dists = new int[size.x, size.y];
        for (int i = 0; i < size.x; i++)
        {
            for (int j = 0; j < size.y; j++)
            {
                dists[i, j] = int.MaxValue;
            }
        }

        var nexts = new PriorityQueue<(int x, int y), int>();

        dists[from.x, from.y] = 0;
        int startPriority = dists[from.x, from.y] + Manhattan(from, to);
        nexts.Enqueue(from, startPriority);

        while (nexts.Count > 0)
        {
            var now = nexts.Dequeue();

            if (now == to) return dists[now.x, now.y];

            var candidates = new[]
            {
                (now.x - 1, now.y),
                (now.x + 1, now.y),
                (now.x, now.y - 1),
                (now.x, now.y + 1)
            };

            foreach (var (x, y) in candidates)
            {
                if (x < 0 || x >= size.x || 
                    y < 0 || y >= size.y || 
                    maps[x][y] == 'X') continue;

                int newDist = dists[now.x, now.y] + 1;

                if (newDist < dists[x, y])
                {
                    dists[x, y] = newDist;
                    int priority = newDist + Manhattan((x, y), to);
                    nexts.Enqueue((x, y), priority);
                }
            }
        }
        
        return -1;
    }

    private int Manhattan((int x, int y) from, (int x, int y) to)
    {
        return Math.Abs(from.x - to.x) + Math.Abs(from.y - to.y);
    }
}