[백준/c++] BOJ 18126 - 너구리 구구

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

18126번: 너구리 구구

 

문제 설명

N개의 방이 있다. 모든 방은 1부터 N까지의 번호가 있고, 입구는 1번이다.

입구는 한 개이며, 모든 방들은 총 N-1개의 길로 서로 오고 갈 수 있다.

최대한 입구에서 먼 방에 아이스크림을 숨기려고 한다. 아이스크림을 숨기려고 하는 방까지 이동하는 거리를 구한다.

N (1 <= N <= 5,000)

A, B, C (1 <= A, B <= N, 1 <= C <= 1,000,000,000)

해결

BFS로 풀까 하다가 백트래킹으로 해결해 주었다.

방과 방이 이어져 있다는 정보는 vector에, 방이 이어진 길의 길이는 board 배열에 저장하였다.

 

입구에서부터 연결된 모든 방을 방문하며, ans보다 멀리 있는 방에 도달한다면 ans를 갱신시켜 주면 된다.

코드

#include<bits/stdc++.h>
using namespace std;

int n;
vector<int> vec[5001];
long long board[5001][5001];
long long ans = 0;
int visited[5001];

void dfs(int start, long long sum) { 
    if (sum > ans) { 
        ans = sum;
    }
    visited[start] = 1;
    for (int i = 0; i < vec[start].size(); i++) {
        int y = vec[start][i];

        if (visited[y] == 0) {
            visited[y] = 1;
            dfs(y, sum + board[start][y]);
            visited[y] = 0;
        }
    }

}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        vec[a].push_back(b);
        vec[b].push_back(a);
        board[a][b] = c;
        board[b][a] = c;
    }
    dfs(1, 0);
    cout << ans;

}