[백준 1240번] 노드사이의 거리 (C++)

문제링크 : https://www.acmicpc.net/problem/1240

1240번: 노드사이의 거리

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N, M, s, e;
vector<pii>t[1001];
int dist[1001];

int bfs(int s, int e)
{
    queue<int>q;
    q.push(s);
    dist[s]=0;
    while(!q.empty())
    {
        int cur = q.front(); q.pop(); //현재 위치
        for(int i=0; i<t[cur].size(); i++)
        {
            auto[next, ncost] = t[cur][i]; //다음 위치와 해당 비용
            if(dist[next]) continue; //이미 방문했다면 스킵
            dist[next] = dist[cur] + ncost; //비용저장
            q.push(next); //다음값 탐색
        }
    }
    return dist[e]; //담긴 비용 반환
}

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

    cin >> N >> M;
    for(int i=0; i<N-1; i++)
    {
        int u, v, cost;
        cin >> u >> v >> cost;
        t[u].push_back({v, cost});
        t[v].push_back({u, cost});
    }
    while(M--)
    {
        cin >> s >> e;
        memset(dist, 0, sizeof(dist));
        cout << bfs(s, e) << "\n";
    }
    
}

트리와 관련된 문제이다.

먼저 양방향 이동이 가능하기에 이에 맞게 입력을 받아준다.

 

그리고 탐색할 두 노드를 입력받고 이에 대해 bfs탐색을 돌려준다.

입력받은 현재 위치를 기준으로 현재 위치에 대한 다음값과 비용을 확인한다.

방문 유무및 거리에 대한 비용을 담을 dist 배열을 이용하여 만약 다음 위치에 해당 값(dist[next])이 있다면 스킵한다.

이는 양방향으로 이동이 가능하기에 예를 들어 3->4로 간 값이 4->3으로 다시 돌아가는 경우가 발생할 수 있는데 이를 방지하기 위함이다.

 

다음 위치를 갈 수 있다면 다음 위치에 대한 비용을 담아주고 이어서 탐색을 돌려준다.

이를 연결된 모든 값에 대해 반복문을 돌려주고 해당 문제의 목표인 e에 담긴 거리값 (dist[e])를 반환해준다.

테스트 케이스가 여러가지이므로 매 테스트케이스마다 비용을 담아주는 dist 배열을 초기화해주어야 한다.