[코딩테스트] 23/12/10 - 미로 찾기 (Level2)

🌜 프로그래머스 링크

문제 설명

1 x 1 크기의 칸들로 이루어진 직사각형 격자 형태의 미로에서 탈출하려고 합니다. 각 칸은 통로 또는 벽으로 구성되어 있으며, 벽으로 된 칸은 지나갈 수 없고 통로로 된 칸으로만 이동할 수 있습니다. 통로들 중 한 칸에는 미로를 빠져나가는 문이 있는데, 이 문은 레버를 당겨서만 열 수 있습니다. 레버 또한 통로들 중 한 칸에 있습니다. 따라서, 출발 지점에서 먼저 레버가 있는 칸으로 이동하여 레버를 당긴 후 미로를 빠져나가는 문이 있는 칸으로 이동하면 됩니다. 이때 아직 레버를 당기지 않았더라도 출구가 있는 칸을 지나갈 수 있습니다. 미로에서 한 칸을 이동하는데 1초가 걸린다고 할 때, 최대한 빠르게 미로를 빠져나가는데 걸리는 시간을 구하려 합니다.

미로를 나타낸 문자열 배열 maps가 매개변수로 주어질 때, 미로를 탈출하는데 필요한 최소 시간을 return 하는 solution 함수를 완성해주세요. 만약, 탈출할 수 없다면 -1을 return 해주세요.

제한사항

• 5 ≤ maps 의 길이 ≤ 100
  • 5 ≤ maps[i]의 길이 ≤ 100
  • maps[i] 는 다음 5개의 문자들로만 이루어져 있습니다.
    • S : 시작 지점
    • E : 출구
    • L : 레버
    • O : 통로
    • X : 벽
  • 시작 지점과 출구, 레버는 항상 다른 곳에 존재하며 한 개씩만 존재합니다.
  • 출구는 레버가 당겨지지 않아도 지나갈 수 있으며, 모든 통로, 출구, 레버, 시작점은 여러 번 지나갈 수 있습니다.

문제풀이

• BFS를 두번사용한다.
  • 시작점에서 레버가기
  • 레버에서 출구 가기

Github 링크

코드 (C++)

struct Pos
{
    int x;
    int y;
    int curTime;
};
bool FindRoot(vector<string> maps, Pos Start, Pos End, int dr[], int dc[], int& value)
{
    queue<Pos> s;
    Start.curTime = value;
    s.push(Start);
    Pos Goal = End;
    int mapSizeY = maps.size();
    int mapSizeX = maps[mapSizeY - 1].size();
    vector<vector<bool>> visited(mapSizeY, vector<bool>(mapSizeX, false));
    while (!s.empty())
    {
        Pos curPos = s.front();
        s.pop();

        if (curPos.x == Goal.x && curPos.y == Goal.y)
        {
            value = curPos.curTime;
            return true;
        }
        for (int i = 0; i < 4; ++i)
        {
            int nx = curPos.x + dr[i];
            int ny = curPos.y + dc[i];
            if (!(ny < maps.size() && nx < maps[ny].size() && maps[ny][nx] != 'X' && !visited[ny][nx]))
            {
                continue;
            }
            
            Pos newPos;
            newPos.x = nx;
            newPos.y = ny;
            visited[ny][nx] = true;
            newPos.curTime = curPos.curTime + 1;
            s.push(newPos);
        }
    }
    return false;
}
int solution(vector<string> maps) {
    int answer = 0;
    Pos Lever;
    Pos Start;
    Pos End;
    int dr[] = {1, -1, 0, 0};
    int dc[] = {0, 0, 1, -1};
    for (int i = 0; i < maps.size(); ++i)
    {
        for (int j = 0; j < maps[i].size(); ++j)
        {
            if (maps[i][j] == 'L')
            {
                Lever.x = j;
                Lever.y = i;
                Lever.curTime = 0;
            }
            if (maps[i][j] == 'E')
            {
                End.x = j;
                End.y = i;
                End.curTime = 0;
            }
            if (maps[i][j] == 'S')
            {
                Start.x = j;
                Start.y = i;
                Start.curTime = 0;
            }
        }
    }
    
    if (!FindRoot(maps, Start, Lever, dr, dc, answer))
        return -1;
    if (!FindRoot(maps, Lever, End, dr, dc, answer))
        return -1;
    return answer;
}