노드사이의 거리(백준 1240)

#include <iostream>
#include <vector>
#include <queue>

using namespace std;
/*
 *1. 노드 수 받기, 노드 쌍 수 받기
 *
 *2. 노드수-1 만큼 인접리스트 만들기(노드, 거리)배열로 넣기pair<int,int>로 하자
 *
 *3. 노드쌍 수 만큼 반복하면서 거리 구하기
 *
 *
 */
int N;
int M;


int find(int s, int e, const vector<vector<pair<int,int>>> store) {
    int node[store.size()+1];
    for(int i=0; i <= store.size()+1; i++) {
        node[i] =0;
    }

    queue<pair<int,int>> q;

    q.push({s,0});
    node[s] =1;

    while(!q.empty()) {
        pair<int,int> cur = q.front(); q.pop();

        int index = cur.first;
        int distance = cur.second;
        node[index]=1;
        for(int i=0; i< store[index].size(); i++) {
            if(node[store[index][i].first]==1)continue;
            if(store[index][i].first ==e) {
                return distance+store[index][i].second;
            }else {
                q.push({store[index][i].first, distance + store[index][i].second});
            }
        }
    }
    return -1;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> M;

    vector<vector<pair<int, int> > > store(N + 1);

    for (int i = 0; i < N - 1; i++) {
        int x, y, distance;
        cin >> x >> y >> distance;

        store[x].push_back({y, distance});
        store[y].push_back({x, distance});
    }

    for (int i = 0; i < M; i++) {
        int s, e;
        cin >> s >> e;

        cout << find(s,e,store)<<"\n";
    }

    return 0;
}

전반적인 로직

간선이 있는 노드 탐색 -> 다익스트라, 벨만포드, 평범한 bfs에서 선택할 수 있었다.

단순히 간선 사이의 거리를 구하는거라서 bfs를 선택했다.
벨만포드는 음수가 있는 경우에 노드간 최단거리
다익스트라는 간선이 양수일 때 최단 거리를 구한다.

노드 사이간 거리를 구하기 위해서 나는 인접 리스트를 선택했다. 그게 쓸데없이 연산을 수행하지 않기 때문이다.
만약에 인접 행렬로 수행하게 된다면 N*N연산을 수행하게 된다.

1. 인접리스트지정하기 (이때 리스트에 들어가는건 단순히 노드뿐만 아니라 해당 점으로 가는 거리도 포함이다)
2. bfs로 두 간선 사이의 거리 구하기

이렇게 크게 두 가지로 나뉠 수 있다.

아무래도 중요한 부분은

2. bfs로 두 간선 사이의 거리 구하기

int find(int s, int e, const vector<vector<pair<int,int>>> store) {
//시작점 s 끝점 e 인접리스트 받기
//지나간 노드를 표시할 node배열 (store보다 사이즈가 1큼 왜냐면 노드가 1부터 시작해서)
    int node[store.size()+1]; 
    // 요청이 들어올때마다 node배열 초기화(처음에 초기화 안해서 통과 못함 tc는 통과가 되도록 설정되어있었음)
    for(int i=0; i <= store.size()+1; i++) {
        node[i] =0;
    }

//bfs탐색을 위핸 Queue선언
    queue<pair<int,int>> q;
//시작점 선언 (시작점, 노드 e로갈때 드는 비용);
    q.push({s,0});
    //시작점 노드는 지나갔다고 선언
    node[s] =1;

    while(!q.empty()) {
    //현재 검사할 노드 N번 노드와 연결된 노드를 찾기위해서 꺼내서 쓰는거임
        pair<int,int> cur = q.front(); q.pop();
//현재 기준점이 되는 노드
        int index = cur.first;
        //시작점에서 기준점 노드로 오는데 드는 비용
        int distance = cur.second;
        //노드 지나갔다고 표시
        node[index]=1;

//현재 노드 N과 연결된 노드들 for문으로 순회
        for(int i=0; i< store[index].size(); i++) {
        //기준점 노드가 이미 지나간 상태면? continue;
            if(node[store[index][i].first]==1)continue;
        //연결된 노드중 도착 노드가 있다면?
            if(store[index][i].first ==e) {
            //현재 거리 + 도착 노드로 가는 거리 return
                return distance+store[index][i].second;
            }else {
            //그게 아니면? 현재 노드에서 인접리스트와 연결된 노드로 이동하는 거리 추가
                q.push({store[index][i].first, distance + store[index][i].second});
            }
        }
    }
    //노드가 중간에 끊긴경우
    return -1;
}

이런식으로 구할 수 있다.
그리 크게 어려운 문제는 아니었던듯하다

REVIEW

#99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL