[BOJ] 1240 - 노드사이의 거리

Sierra·2022년 3월 20일
0

[BOJ] GraphTheory

목록 보기
29/30
post-thumbnail

https://www.acmicpc.net/problem/1240

문제

N(2≤N≤1,000)개의 노드로 이루어진 트리가 주어지고 M(M≤1,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라.

입력

첫째 줄에 노드의 개수 N이 입력되고 다음 N-1개의 줄에 트리 상에 연결된 두 점과 거리(10,000 이하의 정수)를 입력받는다. 그 다음 줄에는 거리를 알고 싶은 M개의 노드 쌍이 한 줄에 한 쌍씩 입력된다.

출력

M개의 줄에 차례대로 입력받은 두 노드 사이의 거리를 출력한다.

예제 입출력

  • 예제 입력 1
4 2
2 1 2
4 3 2
1 4 3
1 2
3 2
  • 예제 출력 1
2
7

Solution

#include <iostream>
#include <vector>
#include <queue>
#define MAX 1001
using namespace std;

vector<pair<int, int>> edge[MAX];
int Dist[MAX];
int BFS(int src, int dst){
    queue<int> q;
    q.push(src);
    while(!q.empty()){
        int x = q.front();
        q.pop();
        for(int i = 0; i < edge[x].size(); i++){
            int nx = edge[x][i].first;
            int cost = edge[x][i].second;
            if(Dist[nx] > 0) continue;
            Dist[nx] = Dist[x] + cost;
            q.push(nx);
        }
    }
    return Dist[dst];
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int N, M; cin >> N >> M;
    for(int i = 0; i < N - 1; i++){
        int src, dst, cost;
        cin >> src >> dst >> cost;
        edge[src].push_back({dst, cost});
        edge[dst].push_back({src, cost});
    }
    for(int i = 0; i < M; i++){
        int src, dst;
        fill_n(Dist, MAX, 0);
        cin >> src >> dst;
        cout << BFS(src, dst) << '\n';
    }
}

처음에 DFS로 풀다가 좀 아닌것 같아서 BFS로 바꾼 문제.
BFS 코딩하는 법 자체는 그렇게 어려운 문제는 아니다. 하지만 이 상황에서 어떻게 BFS를 처리 할 것인가?

입력은 양방향 그래프로 입력받는다. 입력 양식 상 그렇게 처리되어있기에 늘 그렇듯 인접행렬을 vector를 통해 만들어 준다.

#include <iostream>
#include <vector>
#include <queue>
#define MAX 1001
using namespace std;

vector<pair<int, int>> edge[MAX];
int Dist[MAX];
int BFS(int src, int dst){
    queue<int> q;
    q.push(src);
    while(!q.empty()){
        int x = q.front();
        q.pop();
        for(int i = 0; i < edge[x].size(); i++){
            int nx = edge[x][i].first;
            int cost = edge[x][i].second;
            if(Dist[nx] > 0) continue;
            Dist[nx] = Dist[x] + cost;
            q.push(nx);
        }
    }
    return Dist[dst];
}

그 전에 각 노드 별 Dist 데이터를 생성 해 주자. 각 노드들을 탐색했을 때 Cost가 얼마나 발생하였는 지를 확인하는 데이터다. 어쨌든 Tree이기 때문에 아주 복잡하게 이리갔다 저리갔다 할 일은 없기 때문에 특정 노드를 방문했다면 두번 방문할 일은 없기 때문에 Dist[i] > 0 일 때는 continue 처리를 해 준다.

그리고 탐색하고자 하는 Node와 연결되어있는 모든 노드들을 하나씩 방문하며 너비우선탐색을 해 주면 끝이다. 언젠가는 목적지 노드에도 방문 할 것이고 Dist 데이터가 갱신 되어 있겠지.

자주 풀지 않으면 이런 문제도 쉽게 까먹는다. 항상 복습할것.

profile
블로그 이전합니다 : https://swj-techblog.vercel.app/

0개의 댓글