Boj 15971 c++ 두 로봇

그래프탐색의 길로 빠져들었다. 우선은 DFS, 깊이 우선 탐색의 방식으로 풀이하였다. 문제의 조건을 고려하여 예외처리를 해주는 것이 중요한 문제였다. 또한 단순하게 생각하였을 때 문제를 접근할 수 있는 가장 쉬운 방법으로 코드를 짰기 때문에, 이후 개선된 코드를 다시 올려 수정할 예정이다. 제출한 코드는 다음과 같다. 물론 그래프 탐색 관련 문제를 2개 밖에 안풀어봤기에 구글링으로 코드를 수정했다.

#include<iostream>
#include<vector>
#include<algorithm>


using namespace std;
//인접노드 주소, 가중치
vector<vector<pair<int, int>>> G(100001);//각각의 원소 또한 벡터
vector<int> visited(100001);

int N, R1, R2, sum=0;//방의 개수, 두 로봇의 위치
bool found=false;
vector<int> s; // 간선 가중치 저장
void DFS(int V){

    //V가 시작노드


    

     visited[V]=1;

     if(V==R2){
        int Max= *max_element(s.begin(), s.end());
        cout << sum-Max;
        found = true;
        return;
     }

    for(int i=0; i<G[V].size(); i++){
        int next_nod=G[V][i].first;
        int W=G[V][i].second;
        if(!visited[next_nod]){
          
            sum+=W;
            s.push_back(W);
            DFS(next_nod);
            if(found) return;
            sum -= W;
            s.pop_back();
        }
    }
  
}

int main(){
ios_base :: sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);




    cin>>N>>R1>>R2;
    
    if (R1 == R2) {
        cout << 0;
        return 0;
    }

    for(int i=0; i<N-1; i++){
        int A, B, L;//인접노드 2개, 길이

        cin>>A>>B>>L;
        G[A].push_back({B, L});
        G[B].push_back({A, L});
    }
    DFS(R1);



}

우선은 방의 개수, 두 로봇의 현재 위치(노드)를 입력 받아 어떤 두 노드 사이에 간선이 존재하는지 벡터에 저장하였다. 이때, 벡터는 인접 리스트 확인을 위해서 이차원벡터(이런 용어가 있는지는 모른다)로 선언하였다. 때문에 G[i], 즉 벡터의 원소들은 또 다시 벡터로 이루어져 있으며, 이 안에는 연결된 노드의 주소와 가중치가 저장된 쌍들이 저장되어있다. ex) G[i] = {{1, 10}, {2, 4}, .....}
때문에 가장 안쪽에 있는 원소에 접근하기 위해서는 G[V][i].first, G[V][i].second 형태를 사용하면 된다.
 
이후 코드는 DFS이다. 첫번째 로봇이 있는 위치를 입력값으로 하여 DFS함수를 처음으로 호출한다. 이때, 두 로봇이 같은 방에 있으면 함수를 호출하지 않고 바로 0을 출력하는 예외처리를 해주어야만 런타임에러를 방지할 수 있다. 
초기값 노드에서 시작하여 점점더 깊은 노드를 탐색해나간다. 이때, 초기값 노드와 인접한 노드들을 우선으로 탐색하며, 이를 위해 반복문의 반복조건을 i<G[V].size()까지 i++로 해두었다. 이때 G[V]의 크기는 인접 노드의 개수이므로 적합하다.
방문 여부 확인 벡터 또한 만들어 방문되지 않은  인접 노드들만 탐색한다. 또한 탐색과 동시에 두 로봇 사이의 최소 이동 거리를 구하기 위해 가중치를 누적해서 더해간다. 이때, 끝까지 탐색하였음에도 두번째 로봇이 존재하지 않거나 더이상 방문할 노드가 남아있지 않다면 방문 노드들을 스택에서 하나씩 꺼내주어야 하는데, 이때 더하였던 가중치 또한 빼주어야 한다. 때문에 백트래킹을 위해서 재귀 호출 바로 다음 코드에 가중치의 총합에서 부적합 노드의 가중치 값을 빼준다. 이로써 탐색가능한 노드까지 거슬러 올라간 경우에도 가중치 값의 총합을 올바르게 계산할 수 있다. 
 
또한 두번째 로봇의 노드에 도달하였을 때 재귀 호출을 끝내야 하며, 이후의 불필요한 백트래킹 또한 방지해야 하므로 found값에 따라 뒤의 코드 실행 여부를 결정한다. 
또한 최소 이동 거리를 구하기 위해서는 가중치의 합에서 경로중 가장 길었던 간선의 길이를 빼주어야 하므로 가중치 기억 벡터 또한 만들어 값을 적합 노드에 관해서는 저장, 그 이외에는 pop을 수행해준다. 답을 출력할 때에는 그중 최대값을 추출하여 종료한다. 
 

그래프 탐색 문제들을 더 많이 풀어볼 예정