백준 1167: 트리의 지름

📃 문제: 백준 1167(트리의 지름)

1167번: 트리의 지름

 

 

 

🥇 난이도: 골드 2

 

 

 

 

😲 사용한 개념: BFS(너비우선탐색)

DFS(깊이 우선 탐색)	BFS(너비 우선 탐색)
Stack	Queue

 

💡 BFS란?

1️⃣ 탐색 시작 노드 정보를 큐에 삽입하고  pop연산과 동시에 방문처리 한다.
2️⃣ pop한 노드의 인접 노드들 중 방문처리가 되지 않은 노드 정보를 큐에 삽입하고 방문 처리한다.
3️⃣ 인접노드 push가 끝나면, 최상단 노드를 pop하고, 2~3번 과정을 큐가 empty상태가 될 때까지 반복한다.

 

 

 

📖 풀이 사고 과정

 

 

 

👩‍💻 구현 코드(c++ 사용)

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

typedef pair<int, int> edge;
//그래프 저장 배열(A[출발노드]={도착노드, 간선 가중치})
vector<vector<edge>> A;
vector<int> edge_distance;
vector<bool> visited;
int max_index = 0;
void BFS(int start) {
    
    queue<int> myQueue;
    myQueue.push(start);
    visited[start] = true;
    while (!myQueue.empty()) {
        int top = myQueue.front();
        myQueue.pop();
        //출발 노드와 연결되어있는 도착 노드들을 순회
        for (edge e : A[top]) {
            if (!visited[e.first]) {
                myQueue.push(e.first);
                //도착 노드 방문처리
                visited[e.first] = true;
                //(현재 출발 노드까지 누적된 거리)+(새롭게 누적할 거리)
                edge_distance[e.first] = edge_distance[top] + e.second;
                if (edge_distance[max_index] < edge_distance[e.first]) {
                    //2번째 BFS 수행시 필요하므로, max distance인 경우 저장
                    max_index = e.first;
                }
                
            }
        }

    }
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int N, s, e, d;
    cin >> N;

    A.resize(N + 1);

    //누적 거리 저장 배열(distance), 방문 배열(visited)
    edge_distance=vector<int> (N+ 1, 0);
    visited=vector<bool> (N + 1, false);
    //그래프 입력받기(인접리스트)
    for (int i = 1; i <= N; i++) {
        cin >> s;
        while (true) {
            cin >> e;
            if (e == -1) {
                break;
            }
            cin >> d;
            //s: 출발노드, e: 도착노드, d: 간선 가중치
            A[s].push_back(edge(e, d));
        }
    }
    BFS(1);
    //방문배열, 누적 거리 배열 초기화
    fill(visited.begin(), visited.end(), false);
    fill(edge_distance.begin(), edge_distance.end(), 0);
    BFS(max_index);
    sort(edge_distance.begin(), edge_distance.end());
    cout << edge_distance[N] << endl;

    return 0;
}