백준 1240 노드 사이의 거리 C++

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

1240번: 노드사이의 거리

---

문제

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

---

입력

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

---

출력

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

---

해결 방안 -> 

2차원 배열을 map[1000][1000]을 선언하고, 두 노드와 노드 사이의 거리를 입력받고 노드를 연결하고 

map[노드번호1][노드번호2]에 노드사이의 거리를 넣고, 마찬가지로 map[노드번호2][노드번호1]에 노드사이의 거리를 넣어준다.

 

그 후 DFS를 실행하는데 map[현재노드][탐색할노드]가 0이 아니라면 탐색을 하고, map[탐색할노드][현재노드]가 0이라면, map[현재노드][탐색할노드]를 대상으로 DFS를 돌면된다.

---

전체 소스 코드->

#include <iostream>

#include <vector>

using namespace std;

 

//백준 1240 노드사이의 거리

 

vector<int> graph[1001];

bool visited[1001];

int map[1001][1001]; //노드의 거리 저장

int Start,End;

int ans = 0;

 

void init(int n){ // visited배열 초기화

    for(int i = 0;i<=n;i++){

        visited[i] = false;

    }

}

 

void dfs(int start,int depth){

    if(start == End){ //현재 노드가 끝점이라면 ans갱신

        ans = depth;

        return;

    }

    if(visited[start]){

        return;

    }

    visited[start] = true;

    for(int i = 0;i<graph[start].size();i++){

        int y = graph[start][i];

        if(map[start][y] != 0){ //map에 값이 들어 있는 쪽으로 탐색하기

            dfs(y,depth+map[start][y]);

        }

        else if(map[start][y] == 0 && map[y][start] != 0){

            dfs(y,depth+map[y][start]);

        }

    }

 

}

int main(void){

    int n,m;

    cin >> n >> m;

    for(int i = 0;i<n-1;i++){

        int a,b,c;

        cin >> a >> b >> c;

        graph[a].push_back(b);

        graph[b].push_back(a);

        map[a][b] = c; //맵에 노드 사이 거리 저장

        map[b][a] = c;

    }

    for(int i = 0;i<m;i++){

        init(n);

        cin >> Start >> End;

        dfs(Start,0);

        cout << ans << '\n';

    }

}