[C++/1697, 11779] 탐색 중 이전 값를 저장해야 하는 유형의 문제들

경로나 값을 저장해서 다음에 그 값을 참조해야 하는 경우의 문제들을 정리해보자.

대부분 그래프 탐색이나 BFS, DFS 문제에서 경로 찾기, 걸린 시간 등 출발지에서의 값을 가지고 있어야 하는 경우가 많다.

 

1697 문제

아이디어: BFS

현재 값인 N에서 가능한 동작은 3가지이다. +1, -1, 2배 이다. 이 경우로 탐색 가능한 값에 대해서 (현재 값까지 걸린 시간 + 1)을 더해서 저장해두고 이에 대해서 다시 탐색을 도는 방식으로 문제를 해결할 수 있다.

 

이때 저장해두는 값은 시작 노드인 N에서부터 걸린 시간이 된다.

 

구현

// 1697 숨바꼭질
#include <iostream>
#include <queue>
using namespace std;

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int N, K;
    cin>>N>>K;
    
    // 값 저장을 위한 1차원 배열 -> 초기화 필수
    int d[100001] = {0,};
    
    // BFS 시작
    queue<int> q;
    q.push(N);
    d[N] = 1;
    
    while(!q.empty())
    {
        int temp = q.front();
        q.pop();
        
        // 목표 지점이면 출력하고 종료
        if (temp == K)
        {
            cout<<d[temp] - 1<<"\n";
            return 0;
        }
        
        // -1에 대한 동작: 방문하지 않았고 범위 내에 있다면
        if (temp - 1 >= 0 && d[temp - 1] == 0)
        {
            d[temp - 1] = d[temp] + 1;
            q.push(temp - 1);
        }
        
        // +1에 대한 동작: 방문하지 않았고 범위 내에 있다면
        if (temp + 1 <= 100000 && d[temp + 1] == 0)
        {
            d[temp + 1] = d[temp] + 1;
            q.push(temp + 1);
        }
        
        // 2배에 대한 동작: 방문하지 않았고 범위 내에 있다면
        if (temp * 2 <= 100000 && d[temp * 2] == 0)
        {
            d[temp * 2] = d[temp] + 1;
            q.push(temp * 2);
        }
    }
    
    return 0;
}

---

 11779 문제

 

아이디어: 다익스트라

노드에서 다른 노드까지의 최단 경로를 찾는 문제이므로 다익스트라 알고리즘을 사용하여 풀 수 있다.

이때 중요한 점은그 경로를 저장하는 것이다. 이는 어떻게 해결할 수 있을까?

 

먼저 다익스트라 알고리즘은 Greedy 알고리즘이다.  즉 모든 경로까지의 최단 경로를 모두 확인하고 최단인 경우에 대해서 그 노드까지의 거리 값을 업데이트 하는 것이기 때문에, queue에서 빼거나 dist 거리 값을 업데이트할 때 확인한 노드를 저장하는 방식으로 문제를 풀게 되면 최단 경로에 포함되지 않은 노드도 저장하게 된다. 또한 같은 노드가 중복으로 저장될 가능성도 있다.

 

따라서 특정 노드를 방문할 때마다 이 노드의 부모 노드의 값을 저장하는 방식으로 문제를 풀어야 한다. 마지막에는 목적지 노드의 부모 노드를 타고 올라가다 더 이상 부모 노드가 없는 경우 시작 경로에 도달했음을 알 수 있다.

 

따라서 부모 노드 저장을 위한 1차원 배열을 선언하고 0으로 초기화한다.

마지막에 저장된 부모 노드가 0이 아닌 경우 경로가 존재한다는 것이고, 0이 된 경우 시작 경로에 도달했다는 뜻이 된다.

구현

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

vector<pair<int, int>> graph[1001];
// 부모 노드 저장 용도
int route[1001];
int dist[1001];

void dijkstra(int start)
{
    priority_queue<pair<int, int>> pq;
    
    // {가중치, 노드}
    pq.push({0, start});
    dist[start] = 0;
    
    while (!pq.empty())
    {
        int w = pq.top().first * -1;
        int now = pq.top().second;
        
        pq.pop();
        
        if (dist[now] < w)
            continue;

        for(int i = 0;i < graph[now].size();i++)
        {
            int cost = w + graph[now][i].second;
            
            if (cost < dist[graph[now][i].first])
            {
		// 경로 저장을 위해 배열에 현재 노드를 넣어서 부모노드를 체크함
                route[graph[now][i].first] = now;
                
                dist[graph[now][i].first] = cost;
                pq.push({cost * -1, graph[now][i].first});
            }
        }
    }
}
int main()
{
    // N(node), M(edge)
    int N, M;
    cin>>N>>M;
    
    for(int i = 0;i < M;i++)
    {
        int a, b, c;
        cin>>a>>b>>c;
        
        // {노드, 가중치}
        graph[a].push_back({b, c});
    }
    int start, target;
    cin>>start>>target;
    
    fill_n(dist, N + 1, 1e9);
    fill_n(route, 1001, 0);
    
    dijkstra(start);
    
    cout<<dist[target]<<"\n";
    
    stack<int> st;
    st.push(target);
    
    while(1)
    {
        target = route[target];
        if (target == 0)
            break;
        st.push(target);
    }
    
    cout<<st.size()<<"\n";
    while(!st.empty())
    {
        cout<<st.top()<<" ";
        st.pop();
    }
    
    return 0;
}