[C++] Programmers 미로 탈출

문제 설명

 

https://school.programmers.co.kr/learn/courses/30/lessons/81304

프로그래머스

---

내 풀이 과정

첫 번째 시도

문제를 보고 트랩을 밟으면 모든 화살표의 방향이 바뀐다고 생각하였다.

그래서 road_dis[출발점][도착점][트랩의 눌림 여부] 라는 배열을 만들어서 이를 이용한 bfs 탐색 코드를 만들었다.

당연하게도 틀렸다.

문제를 다시 읽고 모든 화살표의 방향이 아니라 "트랩과 연결된" 화살표라는 것을 깨달았다.

 

첫 시도의 코드는 너무 멍청하다고 느껴서 바로 지웠다.

---

두 번째 시도

그래서 어떻게 할까 고민을 하다가 트랩으로 이동하면 트랩과 연결된 화살표의 시작점과 끝점을 바꾸기로 하였다.

다시 말해,

1. 기존의 road_dis 배열을 road_dis[출발점][도착점]으로 만들고,
2. 만약 트랩에 도착하면, road_dis[도착점][출발점] 값과 road_dis[출발점][도착점] 값을 변환하도록 했다.

이렇게 하면 trap을 밟기 전 경로를 계산할 때에는 위의 2번 규칙을 다시 사용해야 하는데 이를 가능하게 하기 위해서 bfs에서 dfs로 변환하였다.

물론 최단경로 문제에는 dfs가 적합하지 않다.

하지만 내가 첫 번째 시도에서 너무 얼빵하게 문제를 풀어서 심신미약 상태였다.

그래서 일단은 지푸라기라도 잡자는 심정으로 코드를 짜보았다.

 

두 번째 코드

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

using namespace std;

const int max_size = 1010;
const int not_visited = 987654321;
int road_dis[max_size][max_size], min_dis[max_size];
bool trap[max_size];

void setting(int n, vector<vector<int>> roads, vector<int> traps) {
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
            road_dis[i][j] = not_visited;
    
    for(int i = 1; i <= n; ++i)
        min_dis[i]= not_visited;
    
    int roads_size = roads.size();
    for(int i = 0; i < roads_size; ++i) {
        int start = roads.at(i).at(0);
        int end = roads.at(i).at(1);
        int distance = roads.at(i).at(2);
        
        road_dis[start][end] = distance;
    }
    
    int traps_size = traps.size();
    for(int i = 0; i < traps_size; ++i)
        trap[traps.at(i)] = 1;
}

void inverted(int n, int now) {
    for(int i = 1; i <= n; ++i) {
        int temp = road_dis[now][i];
        road_dis[now][i] = road_dis[i][now];
        road_dis[i][now] = temp;
    }
}

void dfs(int n, int end, int now, int dis) {
    //printf("새로운 dfs : %d %d\n", now, dis);
    
    if(now == end) {
        min_dis[end] = (dis < min_dis[end] ? dis : min_dis[end]);
        return;
    }
    
    for(int next = 1; next <= n; ++next) {
        if(road_dis[now][next] == not_visited) continue;
        int move = dis + road_dis[now][next];
        if(move >= min_dis[end]) continue;
        
        if(trap[next]) inverted(n, next);
        dfs(n, end, next, move);
        if(trap[next]) inverted(n, next);
    }
}

int solution(int n, int start, int end, vector<vector<int>> roads, vector<int> traps) {
    int answer = 0;
    
    setting(n, roads, traps);
    dfs(n, end, start, 0);
    answer = min_dis[end];
    
    return answer;
}

 

두 번째 결과

(애초에 테케에서 컷당했다.)

---

세 번째 시도

고민을 하다가 결국 dfs를 bfs로 다시 변경하고, 비트마스킹을 사용하여 각 트랩이 눌렸을 때의 상태를 저장하기로 하였다.

왜 하필 비트마스킹을 채택한 근거로는 2가지가 있다.

①트랩의 개수가 10개 이내라는 점

②경로는 어차피 2개의 방의 트랩 정보에 따라 바뀌기 때문에 트랩 정보를 따로 저장할 공간이 필요하다는 점

그래서 queue에 저장할 때 (방 번호), (지금까지 이동한 거리) 뿐만 아니라 (trap이 눌린 정도)도 저장하였다.

 

여담으로 사실 내가 비트마스킹을 제대로 사용해본 적은 처음이다.

20살 때, 내가 프로그래머스 중 한 문제를 풀었을 때, 스스로 비트마스킹 개념을 유추하여 푼 적이 있다.

해결한 당시에는 몰랐지만 같이 알고리즘 스터디를 하는 선배가 "어? 이거 비트마스킹 개념인데?"라고 한 적이 있다.

추후에 해당 문제를 훨씬 깔끔하게 해서 풀어봐야겠다고 생각은 했는데, 생각보다 비트마스킹을 사용한 문제를 많이 접한 적이 없어서 잊어버렸다.

아무튼 이번 기회에 비트마스킹에 대해 깨닫고, 명료하게 정리한 것 같아서 나에겐 의미있는 시도이다.

 

 

세 번째 코드

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

using namespace std;

const int max_size = 1010;
const int not_visited = 987654321;
int road_dis[max_size][max_size], min_dis[max_size][1024];
int trap[max_size];

struct Location {
    int room;
    int dis;
    int state;
};

void setting(int n, vector<vector<int>> roads, vector<int> traps) {
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
            road_dis[i][j] = not_visited;
    
    for(int i = 1; i <= n; ++i)
        for(int j = 0; j < 1024; ++j)
            min_dis[i][j] = not_visited;
    
    for(int i = 1; i <= n; ++i)
        trap[i] = not_visited;
    
    int roads_size = roads.size();
    for(int i = 0; i < roads_size; ++i) {
        int start = roads.at(i).at(0);
        int end = roads.at(i).at(1);
        int distance = roads.at(i).at(2);
        
        road_dis[start][end] = distance;
    }
    
    int traps_size = traps.size();
    for(int i = 0; i < traps_size; ++i)
        trap[traps.at(i)] = i;
}

void bfs(int n, int start, int end, vector<int> traps) {
    queue <Location> location;
    location.push({start, 0, 0});
    
    while(!location.empty()) {
        Location now = location.front();
        location.pop();
        if(now.room == end) continue;
        
        for(int i = 1; i <= n; ++i) {
            int distance;
            if((trap[now.room] != not_visited && (now.state & 1 << trap[now.room])) 
               ^ (trap[i] != not_visited && (now.state & 1 << trap[i])))
                distance = road_dis[i][now.room];
            else distance = road_dis[now.room][i];
            
            if(distance == not_visited) continue;
            
            int temp_dis = now.dis + distance;
            int temp_state = now.state;
            if(trap[i] != not_visited) temp_state ^= (1 << trap[i]);
            
            if(temp_dis < min_dis[i][temp_state]) {
                min_dis[i][temp_state] = temp_dis;
                location.push({i, temp_dis, temp_state});
            }
        }
    }
}

int solution(int n, int start, int end, vector<vector<int>> roads, vector<int> traps) {
    int answer = not_visited;
    
    setting(n, roads, traps);
    bfs(n, start, end, traps);
    
    for(int i = 0; i < (1 << traps.size()); ++i) 
        answer = (answer < min_dis[end][i] ? answer : min_dis[end][i]);
    
    return answer;
}

 

세 번째 결과

틀렸지만 대부분이 시간 초과인 것으로 보아 최적화만 제대로 하면 될 것 같다.

로직 자체는 괜찮은 것 같다.

---

네 번째 시도

사실 이런 종류의 최적화는 문제를 많이 풀어보면서 어떻게 해야 효율적으로 짤 수 있을지 감을 잡는 것도 중요하다.

나는 그동안 vector로 구현하는 것들을 배열로 구현하는 안 좋은 습관이 있어서 감이 많이 없다.

그래서 다른 분들의 코드를 미리 보았다.

내가 참조한 블로그는 바로 다음 블로그이다.

 

https://congsoony.tistory.com/142

프로그래머스 미로 탈출 (2021 카카오 채용연계형 인턴십)

 

 

네 번째 코드

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

using namespace std;
const int room_max_count = 1001;
const int trap_max_count = 1024;
const int not_visited = 987654321;

struct Location {
    int room;
    int cost;
    int state;
};

vector <pair<int, int> > connected[trap_max_count][room_max_count];
int trap[room_max_count];
int min_dis[trap_max_count][room_max_count];

void setting(int room_count, vector<vector<int>> roads, vector<int> traps) {
    for(int i = 1; i <= room_count; ++i) trap[i] = -1;
    for(int i = 0; i < traps.size(); ++i) trap[traps[i]] = i;
    
    for(int state = 0; state < (1 << traps.size()); ++state) {
        for(auto &road : roads) {
            int start = road[0];
            int end = road[1];
            int distance = road[2];
            
            if( (trap[start] != -1 && (state & 1 << trap[start])) 
               ^(trap[end] != -1 && (state & 1 << trap[end])) )
                swap(start, end);
            
            connected[state][start].push_back({end, distance});
        }
    }
    
    for(int i = 0; i < (1 << traps.size()); ++i)
        for(int j = 1; j <= room_count; ++j)
            min_dis[i][j] = not_visited;
}

void bfs(int room_size, int start, int end) {
    min_dis[0][0] = 0;
    queue<Location> location;
    location.push({start, 0, 0});
    
    while(!location.empty()) {
        Location now = location.front();
        location.pop();
        
        for(auto &road : connected[now.state][now.room]) {
            int next_room = road.first;
            int next_cost = now.cost + road.second;
            int next_state = now.state;
            if(trap[next_room] != -1) next_state ^= (1 << trap[next_room]);
            
            
            if(next_cost < min_dis[next_state][next_room]) {
                min_dis[next_state][next_room] = next_cost;
                location.push({next_room, next_cost, next_state});
            }
        }
    }
}

int solution(int n, int start, int end, vector<vector<int>> roads, vector<int> traps) {
    int answer = not_visited;
    
    setting(n, roads, traps);
    bfs(n, start, end);
    
    for(int i = 0; i < (1 << traps.size()); ++i)
        answer = (answer < min_dis[i][end] ? answer : min_dis[i][end]);
    
    return answer;
}

 

네 번째 결과

---

다른 사람들의 코드를 보며..

놀랐다.

거의 모든 사람들이 비트마스크와 vector 활용을 매우 자유자재로 하였다.

내가 생각보다 견해가 좁다는 사실을 깨달았다.

 

기본 로직 자체는 내 1~3번째 시도와 비슷하지만 이를 각자의 방법으로 가독성 좋게 구현하였다.

그리고 다른 사람들의 코드를 보고 내 코드에서 좀 더 보완해야겠다고 생각한 디테일도 있다.

그나마의 시간을 최적화하기 위한 우선순위 큐가 바로 그 디테일이다.

좀 더 겸손해져야겠다.