[프로그래머스] level.2 - 미로 탈출(C++)

https://school.programmers.co.kr/learn/courses/30/lessons/159993#qna

내 해답

문제 접근은 쉽지만, 시간 복잡도 때문에 고생한 문제이다.

문제에는 ‘출구는 레버가 당겨지지 않아도 지나갈 수 있으며, 모든 통로, 출구, 레버, 시작점은 여러 번 지나갈 수 있습니다.’ 라고 적혀있는데 내 방식에서는 이게 함정이 되었다.

목적지는 레버와 출구 2개가 있는데 각 목적지까지 가는 길에 재방문은 안된다. 그러니까 (시작점→레버) , (레버→ 출구) 경로에 재방문을 허용하면 너무 느리다.

따라서 (시작점→레버) + (방문 기록 초기화) + (레버→ 출구) 이런 식으로 해결했다. 결국 하나의 q에서 BFS를 두 번 도는 형식으로 해결한 것이다.

#include <string>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int solution(const vector<string> maps) {
    int answer = -1;

    vector<vector<int>> visit(maps.size(), vector<int>(maps[0].size(), 0));
    queue<pair<int, int>> q;
    
    int start_x = -1, start_y = -1;
    int dx[] = {1, -1, 0, 0};
    int dy[] = {0, 0, 1, -1};
    bool lever = false;
    
    // 시작점 찾기
    for(int y = 0; y < maps.size(); ++y)
    {   
        for(int x = 0; x < maps[0].size(); ++x)
        {
            if(maps[y][x] == 'S')
            {
                start_x = x;
                start_y = y;
                break;
            }
        }
        if(start_x != -1)
            break;
    }
    
    // q에 시작점 추가
    q.push({start_x, start_y});
    while(!q.empty())
    {
        int x = q.front().first;
        int y = q.front().second;
        
        q.pop();
        
        // 레버가 올라간 상태에서 탈출구를 만났을 때
        if(lever && 'E' == maps[y][x] )
        {
            answer = visit[y][x];
            break;
        }
        
        // 아직 레버가 안올라간 상태에서 레버를 만났을 때
        else if(!lever && 'L' == maps[y][x])
        {
            lever = true;
            int time = visit[y][x];
            
            // q와 visit 초기화
            q = queue<pair<int, int>>();
            fill(visit.begin(), visit.end(), vector(visit[0].size(), 0));
            
            // lever 까지 걸린 시간 설정
            visit[y][x] = time; 
        }
        
        // 다음 방문지 찾기
        for(int i = 0; i < 4; ++i)
        {
            int nx = x+dx[i];
            int ny = y+dy[i];
            
            if(nx >= 0 && ny >= 0 && nx < maps[0].size() && ny < maps.size())
                if(maps[ny][nx] != 'X' && visit[ny][nx] == 0)
                {
                    q.push({nx, ny});       
                    visit[ny][nx] = visit[y][x] + 1;
                }
        }
    }

    return answer;
}