C# 미로 탈출 - BFS 길찾기 / 프로그래머스 [Lv.2]

출처: 프로그래머스 코딩 테스트 연습
https://school.programmers.co.kr/learn/courses/30/lessons/159993

 

 

나의 풀이

public int solution(string[] maps) 
{
    var startPoint = FindChar(maps, 'S');

    int dist = MoveTo(maps, 'L', startPoint, out var leverPoint);
    if(dist == -1)
        return -1;
    else
    {
        int dist2 = MoveTo(maps, 'E', leverPoint, out var _);
        return dist2 == -1 ? -1 : dist + dist2;
    }
}

private (int, int) FindChar(string[] maps, char c)
{
    for(int y = 0; y < maps.Length; ++y)
    {
        int x = maps[y].IndexOf(c);
        if(x != -1)
            return (y, x);
    }
    return (-1, -1);
}

private int MoveTo(string[] maps, char target, (int y, int x) start, out (int, int) end)
{
    int[] dy = { 0, 0, -1, 1 };
    int[] dx = { -1, 1, 0, 0 };

    var dist = new int[maps.Length, maps[0].Length];
    var queue = new Queue<(int, int)>();
    queue.Enqueue(start);

    while(queue.Count > 0)
    {
        (int y, int x) cur = queue.Dequeue();
        if(maps[cur.y][cur.x] == target) // 도달
        {
            end = cur;
            return dist[cur.y, cur.x];
        }

        for(int i = 0; i < 4; ++i)
        {
            int moveToY = cur.y + dy[i];
            int moveToX = cur.x + dx[i];

            if(moveToY >= maps.Length || moveToY < 0) continue;
            if(moveToX >= maps[0].Length || moveToX < 0) continue;

            if(maps[moveToY][moveToX] == 'X') continue;
            if(dist[moveToY, moveToX] != 0) continue;

            queue.Enqueue((moveToY, moveToX));
            dist[moveToY, moveToX] = dist[cur.y, cur.x] + 1;
        }
    }

    end = (-1, -1);
    return -1;
}

이전에 풀었던 게임 맵 최단거리 문제랑 똑같은데 이동하는 게 2번일 뿐이다.

2023.03.04 - [코딩 테스트] - C# 게임 맵 최단거리 - BFS 길찾기 / 프로그래머스 [Lv.2]

 

그때 거리를 테이블로 관리하는 방식이 깔끔해 보여서 2차원 배열로 거리를 관리하는 방식으로 풀었다.

visited 대신 거리테이블의 값이 0일 때 탐색한다.

 

 

세부적인 최적화.

 - 큰 성능 차이는 없을 거라 생각해서 성능 최적화를 크게 안했는데, 대표적으로 'X'가 아닐 경우에 탐색하기 때문에 시작지점에서 시작해서 다시 시작지점으로 돌아가는 경우도 발생한다.

 

다른 풀이가 있다면.

 - 시작지점과 끝지점을 알고있기 때문에 양방향에서 BFS로 탐색하면 성능 상 더 이득일 것이다. 코드가 늘어나겠지만.

 

멤버 변수에 대해.

 - 나는 기본적으로 멤버변수를 사용하지 않는 것을 전제로 풀고 있다. 코딩테스트 때 멤버 변수를 사용하는것이 성능적으로 이득이지만 실제 프로젝트에서는 코드를 작성할 때 함수마다 멤버변수를 남용하면 코드가 섞이는 경우가 많기 때문.