백준 18126 너구리 구구 C++

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

18126번: 너구리 구구

---

문제

텔레토비 동산에 사는 너구리 구구는 입구, 거실, 주방, 안방, 공부방, 운동실, 음악실, 음식 창고 등 N개의 방을 가지고 있다. 입구를 포함한 모든 방은 1부터 N까지의 번호가 있고, 입구는 1번이다.  구구의 집으로 들어가는 입구는 한 개이며 입구과 모든 방들은 총 N-1개의 길로 서로 오고 갈 수 있다.

구구는 스머프 동산에서 멜론아 아이스크림을 발견했다. 구구는 무더운 여름 햇살을 피해 최대한 입구에서 먼 방에 아이스크림을 숨기려고 한다.

구구가 집 입구에서 멜론아 아이스크림을 숨기려고 하는 방까지 이동하는 거리를 구하여라.

---

입력

첫째 줄에 정수 N(1 ≤ N ≤ 5,000)이 주어진다.

다음 N-1개의 줄에 구구의 집의 모든 길의 정보가 정수 A, B, C(1 ≤ A, B ≤ N, 1 ≤ C ≤ 1,000,000,000)로 주어진다.

A번 방과 B번 방 사이를 양방향으로 연결하는 길의 길이가 C임을 의미한다.

---

출력

구구가 집 입구에서 멜론아 아이스크림을 숨기려고 하는 방까지 이동하는 거리를 구하여라.

---

너구리 구구는 N개의 방을 가지고 있습니다. 방은 1번부터 N번까지 번호가 존재하고, 입구는 1번입니다.

입구와 모든 방들은 N-1개의 길이 있고 양방향입니다.

 

입구에서 가장 먼 방에 아이스크림을 숨기는데, 입구에서 아이스크림을 숨기려는 방까지 이동해야 하는 거리를 구해야 합니다.

 

예를들어 방이 4개있고, 1번과 2번방이 길이가 3인 양방향인 길이 존재하고, 2번방과 3번방은 길이가 2인 양방향의 길이,

2번방과 4번방은 길이가 4인 양방향의 길이 존재합니다.

 

이 경우 입구에서 가장 먼 방은 4번방이고 1-2-4로 간다면, 7의 길이를 이동하게 됩니다.

 

4
1 2 3
2 3 2
2 4 4

 

먼저 방을 입력받고, 양방향 길을 만들어주었습니다.

void init(){
    
    //총 방의 개수 N
    cin >> n;
    
    for(int i = 0;i<n-1;i++){
        int a,b,c;
        cin >> a >> b >> c;
        map[a][b] = c;
        map[b][a] = c;
        //a와 b를 연결하고, b와 a를 연결(양방향), 길이를 map2차원 배열에 저장
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
}

그 후, DFS를 진행하는데, 

현재 방의 모든 자식들을 대상으로, 백트래킹을 해서, 가장 긴 길을 찾아서 갱신하게 만들었습니다.

 

void dfs(int start,long long sum){ //start->현재 방, sum -> 길이 갱신

    if(sum > ans){ // 최장 길이 갱신
        ans = sum;
    }
    visited[start] = 1; //현재 방 방문처리
    
    for(int i = 0;i<graph[start].size();i++){ //방의 자식들을 대상으로 백트래킹 실행
        int y = graph[start][i];
        
        //백트래킹 코드
        if(visited[y] == false){
            visited[y] = true;
            dfs(y,sum+map[start][y]);
            visited[y] = false;
        }
    }
    
}

전체 코드입니다 ->

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

vector<int> graph[5001];
bool visited[5001];
int map[5001][5001];
int n;
long long ans = 0;


void init(){
    
    //총 방의 개수 N
    cin >> n;
    
    for(int i = 0;i<n-1;i++){
        int a,b,c;
        cin >> a >> b >> c;
        map[a][b] = c;
        map[b][a] = c;
        //a와 b를 연결하고, b와 a를 연결(양방향), 길이를 map2차원 배열에 저장
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
}

void dfs(int start,long long sum){ //start->현재 방, sum -> 길이 갱신

    if(sum > ans){ // 최장 길이 갱신
        ans = sum;
    }
    visited[start] = 1; //현재 방 방문처리
    
    for(int i = 0;i<graph[start].size();i++){ //방의 자식들을 대상으로 백트래킹 실행
        int y = graph[start][i];
        
        //백트래킹 코드
        if(visited[y] == false){
            visited[y] = true;
            dfs(y,sum+map[start][y]);
            visited[y] = false;
        }
    }
    
}
int main(void){
    init();
    dfs(1,0);
    cout << ans;
}