[알고리즘] 미로탈출

https://school.programmers.co.kr/learn/courses/30/lessons/159993?language=cpp

프로그래머스

 

간단한 BFS문제입니다. 특이점이라면 시작점에서 레버까지한번, 레버에서 도착지까지 한번 두번 BFS를 해야한다는 점이겠네요

 

이것을 모듈로 분리하는 것이 좋아보이긴 하지만 저는 일단 그냥 별도로 했습니다.

using namespace std;

int N, M;

struct Point
{
    int r, c, dist;
};

int solution(vector<string> maps) {
    int answer = 0;

    N = maps.size();
    M = maps[0].size();

    vector<vector<bool>> visited1(N, vector<bool>(M, false));
    vector<vector<bool>> visited2(N, vector<bool>(M, false));
    int sr = 0, sc = 0;
    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < M; ++j)
        {
            char cur = maps[i][j];
            if (cur == 'S')
            {
                sr = i;
                sc = j;
            }
            else if (cur == 'X')
            {
                visited1[i][j] = true;
                visited2[i][j] = true;
            }
        }
    }

    queue<Point> q;
    q.push({ sr, sc, 0 });

    int dr[4] = { -1, 0, 1, 0 };
    int dc[4] = { 0, -1, 0, 1 };

    bool flag = false;
    while (!q.empty())
    {
        auto[r, c, dist] = q.front();
        q.pop();
        for (int i = 0; i < 4; ++i)
        {
            int nr = r + dr[i];
            int nc = c + dc[i];
            if (nr >= 0 && nr < N && nc >= 0 && nc < M && !visited1[nr][nc])
            {
                if (maps[nr][nc] == 'L')
                {
                    flag = true;
                    sr = nr;
                    sc = nc;
                    break;
                }
                visited1[nr][nc] = true;
                q.push({ nr, nc, dist + 1 });
            }
        }
        if (flag)
        {
            answer += dist + 1;
            break;
        }
    }

    if (!flag)
        return -1;

    flag = false;

    queue<Point> q2;
    q2.push({ sr, sc, 0 });
    while (!q2.empty())
    {
        auto [r, c, dist] = q2.front();
        q2.pop();

        for (int i = 0; i < 4; ++i)
        {
            int nr = r + dr[i];
            int nc = c + dc[i];
            if (nr >= 0 && nr < N && nc >= 0 && nc < M && !visited2[nr][nc])
            {
                if (maps[nr][nc] == 'E')
                {
                    flag = true;
                    break;
                }
                visited2[nr][nc] = true;
                q2.push({ nr, nc, dist + 1 });
            }
        }
        if (flag)
        {
            answer += dist + 1;
            break;
        }
    }
    if (!flag)
        return -1;
    return answer;
}