[프로그래머스/C++] GPS (2017 카카오코드 본선)

 

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 정정횟수를 어떻게 하면 최소 횟수로 줄일 수 있는지를 계산하는 문제다.

 

중요한 점은 시간 순서대로 탐색하면서 시간을 고치는게 최선이 아니라는 점이다.

올바르게 정해진 이동경로를 고치는게 오히려 더 정정횟수가 적을 수 있다.

 

그래서 처음에 이 문제를 보고 BFS로 풀면서 memoization을 활용해 시간을 줄여야 겠다는 생각이 들었다.

 

먼저 경로를 정정하거나 정정하지 않은 경우를 queue에 넣고, BFS로 특정 시간에 어느 지점을 방문했을 때 정정횟수가 최소인 경우를 계속 저장하면서 문제를 풀었다.

 

이 과정에서 BFS를 실행하면 정정 횟수가 최소인 경우가 아님에도, BFS 탐색을 할 경우가 생길 수 있으므로, queue에 들어있는 정정횟수가 현재 저장된 최소 횟수와 일치할 경우만 실행하도록 가지치기를 해서 문제를 풀었다.

 

이후 탐색을 완료한 다음 t시간에 목적지에 도달했을 때 정정 횟수를 return하도록 코드를 짰다.

 

이렇게 코드를 짜고 나니까 굳이 queue를 이용하지 않아도 된다는 생각이 들었다.

 

queue를 이용하지 않은 풀이는 다음과 같다.

 

1. t 시간에 방문할 수 있는 경로에 대해 다음 경로들을 전부 탐색해 이동 경로를 정정한 최소 횟수를 저장한다.

    (t+1시간에 방문할 수 있는 경로들 탐색 완료)

 

2. t+1시간에 방문 가능한 경로가 전부 갱신이 됐으므로, t+1시간에 방문할 수 있는 경로에 대해 다음 경로들을 전부 탐색하고 이동 경로를 정정한 최소 횟수를 계산해 t+2시간에 방문할 수 있는 지점들에 대한 최소 횟수를 저장한다. 

 

잘 생각해 보면, BFS로 t 시점에대해 다음에 방문 가능한 경로들에 대해 최소 정정 횟수를 계산해 queue에 넣는 방법을 반복 하는 방법과 queue에 넣지 않고 바로 반복하는게 똑같은 과정이다.

 

두 방법 모두 memoization을 활용한 방법으로 최종적으로 t시간에 목적지에 저장된 이동경로의 최소 정정 횟수를 return하면 된다.

​

[아이디어 정리]

1. t 시점에서 방문할 수 있는 경로들을 탐색하고 gps_log와 다르다면 경로를 정정한 횟수를 1 늘리고 memoization을 활용해 최소 횟수를 2차원 vector에 저장한다
2. 위 과정을 반복해 최종적으로 t 시점에 목적지 지점에 저장된 이동 경로의 최소 정정 횟수를 return한다.
3. 만약 목적지에 방문할 수 있는 방법이 없다면 -1을 return한다.

 

 

Code

 

#include <vector>
using namespace std;

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
// n 거점 개수, m 도로 개수, k 거점 정보 개수, edgelist 그래프 정보 
int solution(int n, int m, vector<vector<int>> edge_list, int k, vector<int> gps_log) {
    vector<vector<int>> DP(k+1,vector<int>(n+1,101)); // 오류 수정 횟수 //앞이 시간
    vector<vector<int>> graph(n+1);
    for (int i=1; i<n+1; i++)
    {
        graph[i].push_back(i);
    }
    for (int i=0; i<edge_list.size(); i++)
    {
        graph[edge_list[i][0]].push_back(edge_list[i][1]);
        graph[edge_list[i][1]].push_back(edge_list[i][0]);
    }
    DP[0][gps_log[0]]=0;
    for (int t=0; t<k-1; t++)
    {
        for (int i=1; i<n+1; i++)
        {
            if (DP[t][i]!=101)
            {
                for (int j=0; j<graph[i].size(); j++)
                { //다음 원소
                    if (DP[t+1][graph[i][j]]>=DP[t][i]+1)
                    {
                        if (gps_log[t+1]!=graph[i][j])
                        {
                            DP[t+1][graph[i][j]]=DP[t][i]+1;
                        }
                        else
                        {
                            DP[t+1][graph[i][j]]=DP[t][i];
                        }
                    }
                }
            }
        }
    }
    if (DP[k-1][gps_log[k-1]]==101)
    {
        DP[k-1][gps_log[k-1]]=-1;
    }
    return DP[k-1][gps_log[k-1]];
}

 

 

 

Code (BFS)

#include <vector>
#include <queue>
using namespace std;

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
// n 거점 개수, m 도로 개수, k 거점 정보 개수, edgelist 그래프 정보 
int solution(int n, int m, vector<vector<int>> edge_list, int k, vector<int> gps_log) {
    vector<vector<int>> DP(k+1,vector<int>(n+1,101)); // 오류 수정 횟수 //앞이 시간
    vector<vector<int>> graph(n+1);
    for (int i=1; i<n+1; i++)
    {
        graph[i].push_back(i);
    }
    for (int i=0; i<edge_list.size(); i++)
    {
        graph[edge_list[i][0]].push_back(edge_list[i][1]);
        graph[edge_list[i][1]].push_back(edge_list[i][0]);
    }
    queue<vector<int>> Q;
    vector<int> a(3,0); // 위치, 시간, 정정 횟수 
    vector<int> nv,sv;
    DP[0][gps_log[0]]=0;
    a[0]=gps_log[0];
    Q.push(a);
    while (!Q.empty())
    {
        nv=Q.front();
        Q.pop();
        if (nv[1]==k-1)
        {
            break;
        }
        if (DP[nv[1]][nv[0]]==nv[2])
        {
            for (int i=0; i<graph[nv[0]].size(); i++)
            {
                sv=nv;
                sv[1]+=1;         
                sv[0]=graph[nv[0]][i];
                if (graph[nv[0]][i]!=gps_log[sv[1]])
                {
                    sv[2]+=1; //gps와 틀리면 정정 횟수 +1,  
                } 
                if (DP[nv[1]+1][graph[nv[0]][i]]>sv[2])
                {
                    DP[nv[1]+1][graph[nv[0]][i]]=sv[2];
                    Q.push(sv);
                }
            }
        }        
    }
    if (DP[k-1][gps_log[k-1]]==101)
    {
        DP[k-1][gps_log[k-1]]=-1;
    }
    return DP[k-1][gps_log[k-1]];
}

 

 

---

 

queue를 이용해 풀었던 처음 풀이는 queue에 push와 pop과정이 계속 일어나고 가지치기를 위해 비교하는 코드가 있기 때문에 queue를 쓰지 않은 풀이에 비해 생각보다 느리다.

BFS로 풀 때, 처음에 -1의 경우도 빼먹고, 변수 이름도 잘못 사용해 바로 안풀렸다... 만약 변수 이름이랑 -1 때문에 시간 많이 썼으면 억울했을 듯;;

 

프로그래머스