[C++] Programmers 미로 탈출 풀이 (2021 카카오 채용연계형 인턴십)

(시도 1)

코드

처음에는 단순히 graph를 변경하여 "Back Tracking" 방식으로 풀면 될 것 같아, 아래와 같이 코드를 짰다.

#include <string>
#include <vector>
#include <limits.h>
#include <algorithm> 

using namespace std;

void transpose_graph (int n, vector<vector<int>> &graph, int k) {
    vector<int> temp = graph[k];
    vector<int> col;
    
    for (int i = 0; i < n; i++) {
        col.push_back(graph[i][k]);
        graph[i][k] = temp[i];
    }
    
    graph[k] = col;
} 


void DFS(int n, vector<vector<int>> graph, vector<int> traps, int cur, int target, int shortcut, int* answer) {
    if (cur == target) {
        *answer = *answer < shortcut ? *answer : shortcut;
        return;
    }
    
    for (int i = 0; i < n; i++) {
        int dist = graph[cur][i];
        if (!dist) continue;
        
        if (find(traps.begin(), traps.end(), i+1) != traps.end()) {  // i is trap
            transpose_graph(n, graph, i);
            DFS(n, graph, traps, i, target, shortcut+dist, answer);
            transpose_graph(n, graph, i);            
        } else {
            DFS(n, graph, traps, i, target, shortcut+dist, answer);
        }
    }
    return;
}

int solution(int n, int start, int end, vector<vector<int>> roads, vector<int> traps) {
    int answer = INT_MAX;
    vector<vector<int>> graph (n, vector<int> (n, 0));
    for (int i = 0; i < roads.size(); i++) {
        vector<int> road = roads[i];
        graph[road[0]-1][road[1]-1] = road[2];
    }

    DFS(n, graph, traps, start-1, end-1, 0, &answer);
    
    return answer;
}

하지만, 방문 유무를 체크하는 부분이 없어서 무한으로 재귀함수를 호출하고 있었다. 결과적으로 테스트 시 답도 틀리고 시간초과도 많이 났다.

(시도 2)

코드

방문 유무를 체크하는 부분(visit)을 vector형태로 구현하고, visit[i][j]를 i->j 방문 최소 경로를 저장하도록 하였다. 추가로, graph를 함수 매개변수로 전달해서 그런지 여전히 테스트에서 시간 초과가 많이 뜨길래 graph, visit는 전역변수로 선언해주었다. 또한 두 노드(Node)간 여러 경로가 있을 수 있다고 명시되어 있으니 최소 값만 저장하도록 하였다.

#include <string>
#include <vector>
#include <limits.h>
#include <algorithm> 

using namespace std;

vector<vector<int>> graph;
vector<vector<int>> visit;

void transpose_graph (int n, vector<vector<int>> &graph, int k) {
    vector<int> temp = graph[k];
    vector<int> col;
    
    for (int i = 0; i < n; i++) {
        col.push_back(graph[i][k]);
        graph[i][k] = temp[i];
    }
    graph[k] = col;
} 


void DFS(int n, vector<int> traps, int cur, int target, int cur_dist) {

    for (int i = 0; i < n; i++) {
        int next_dist = graph[cur][i];
        if (next_dist==INT_MAX) continue;
        
        if (visit[cur][i] > cur_dist + next_dist) {
            visit[cur][i] = cur_dist + next_dist;
            if (find(traps.begin(), traps.end(), i+1) != traps.end()) {
                transpose_graph(n, graph, i);
                DFS(n, traps, i, target, visit[cur][i]);
                transpose_graph(n, graph, i); 
            } else {
                DFS(n, traps, i, target, visit[cur][i]);
            }
        } 
    }
    return;
}

int solution(int n, int start, int end, vector<vector<int>> roads, vector<int> traps) {

    graph.assign(n, vector<int> (n, INT_MAX));
    visit.assign(n, vector<int> (n, INT_MAX));
    
    for (int i = 0; i < roads.size(); i++) {
        vector<int> road = roads[i];
        graph[road[0]-1][road[1]-1] = min(graph[road[0]-1][road[1]-1], road[2]);
    }
    DFS(n, traps, start-1, end-1, 0);

    int answer = INT_MAX / 2 - 1;
    for (int i = 0; i < n; i++) {
        answer = answer < visit[i][end-1] ? answer : visit[i][end-1];
    }
    return answer;
}

결과 

모든 결과 값은 시간 초과 없이 출력되기는 하나, 4문제 (3, 5, 6, 7 번)에 대해서 오답을 출력했다. 이는 노드(Node)간 쌍방향 경로가 있는 경우 visit[i][j]에 잘못된 최소 값이 저장되어있을 수 있음을 깨닫고, visit는 단순히 vertex의 숫자가 아닌 연결상태에 따른 최소값을 저장할 수 있게 구조를 잡았다.

(시도 3)

코드

#include <string>
#include <vector>
#include <map>
#include <limits.h>
#include <algorithm> 

using namespace std;

vector<vector<pair<int,int>>> graph;
vector<map<vector<pair<int, int>>, int>> visit;

void transpose_graph (int n, vector<vector<pair<int,int>>> &graph, int k) {
    vector<pair<int,int>> temp = graph[k];
    vector<pair<int,int>> col;
    
    for (int i = 0; i < n; i++) {
        col.push_back(graph[i][k]);
        graph[i][k] = temp[i];
    }
    graph[k] = col;
} 


void DFS(int n, vector<int> traps, int cur, int dist) { 

    if (find(traps.begin(), traps.end(), cur+1) != traps.end())
        transpose_graph(n, graph, cur);

    if (visit[cur].find(graph[cur]) == visit[cur].end() ||
        visit[cur][graph[cur]] > dist) {
        visit[cur][graph[cur]] = dist;
        for (int next = 0; next < n; next++) {
            if (graph[cur][next].first != INT_MAX) {
                DFS(n, traps, next, dist + graph[cur][next].first);
            }
        }     
    }
    
    if (find(traps.begin(), traps.end(), cur+1) != traps.end())
        transpose_graph(n, graph, cur);
    
    return;
}

int solution(int n, int start, int end, vector<vector<int>> roads, vector<int> traps) {

    graph.assign(n, vector<pair<int, int>> (n, {INT_MAX, 0}));
    visit.assign(n, {});
    
    for (int i = 0; i < roads.size(); i++) {
        vector<int> road = roads[i];
        if (graph[road[0]-1][road[1]-1].first > road[2]) {
            graph[road[0]-1][road[1]-1] = {road[2], i};
        }
    }
    DFS(n, traps, start-1, 0);

    int answer = INT_MAX;
    for(auto& it : visit[end-1]){
        answer = min(answer, it.second);
    }

    return answer;
}

결과

성공!