2467. Most Profitable Path in a Tree

https://leetcode.com/problems/most-profitable-path-in-a-tree/description/

 

 

문제 이해

문제에서 요구하는 바는 이렇다.

Alice는 노드 0에서 출발해서, 리프 노드까지 도달한다.

Bob은 주어진 노드에서 출발해서, 노드 0까지 도달한다.

이 과정 속에서, Alice가 가질 수 있는 최대 보상 값을 구하는 문제였다.

 

우선, 보상 값을 구할 때 세가지 다른 케이스가 존재했다.

1. Alice가 해당 노드에 먼저 도착한 경우: 해당 보상을 그대로 얻는다.
2. Bob이 먼저 해당 노드에 도착한 경우: 보상을 획득하지 못한다.
3. 둘이 동시에 도착한 경우: 현재 보상 / 2를 얻는다.

이러한 문제 흐름을 먼저 해결하기 위해선, Bob이 각 노드에 도착하는 시간을 먼저 계산해줘야 했다.

 

특정 목적지 까지 경로를 탐색할 때

나는 처음에 단순하게 BFS를 사용해서 해당 노드까지 걸리는 시간을 계산했다. 하지만, 이렇게 되면 불필요한 경로 계산을 해버리고 만다.

 

`3 -> 1 -> 0`의 경로가 Bob이 노드 0까지 도달하는 경로인데, 이 과정에서 노드 `2`나 `4`는 불필요하다.

 

다른 사람의 코드와 gpt를 참고한 결과 DFS를 사용하여 탐색하고, 백트래킹처럼 구현을 했다. 종료 조건은 노드 `0`을 만날 때고, 안쓰는 경로 같은 경우엔 -1로 초기화를 해줘 해당 경로는 사용되지 않음을 표시했다.

 

Alice로부터 탐색 진행

이 과정은 간단했다. BFS를 돌면서 Alice의 현재 시간과 Bob이 해당 노드를 도착하는데 걸리는 시간을 비교하여 보상을 계산해줬다.

단, Bob의 시간이 -1인 경우 (도달하지 않은 경우)도 생각해줘야 했다.

 

그리고 우리는 `Leaf` 노드일 때의 최댓값을 구해야하므로 boolean 값을 선언해서 판별해주고, 최댓값을 갱신해주었다.

 

 

정답 코드

class Solution {
    int n;
    int [] bob_time;
    boolean [] bob_visited;
    List<List<Integer>> graph = new ArrayList<>();
    int max = Integer.MIN_VALUE;
    public int mostProfitablePath(int[][] edges, int bob, int[] amount) {
        n = edges.length + 1;
        bob_time = new int[n+1];
        bob_visited = new boolean[n+1];

        Arrays.fill(bob_time, -1);
        bob_time[bob] = 0;

        for(int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }
        for(int [] edge : edges) {
            graph.get(edge[0]).add(edge[1]);
            graph.get(edge[1]).add(edge[0]);
        }

        calculateBob(bob, bob_time);
        // for(int i = 0; i < n; i++) {
        //     System.out.print(bob_time[i] + " ");
        // }
        calculateIncome(amount);
        return max;
    }

    public boolean calculateBob(int bob, int[] bob_time) {
        if (bob == 0) { // 노드 0에 도착했을 때 
            return true;
        }

        bob_visited[bob] = true;
        for(int nxt : graph.get(bob)) {
            if (!bob_visited[nxt]) {
                bob_time[nxt] = bob_time[bob] + 1;
                if (calculateBob(nxt, bob_time)) {
                    return true;
                }
                bob_time[nxt] = -1;
            }
        }
        return false;
    }

    public void calculateIncome(int[] amount) {
        boolean [] visited = new boolean[n + 1];
        visited[0] = true;
        Queue<int []> q = new LinkedList<>();
        q.add(new int[]{0, amount[0] , 0}); // 현재노드, reward, time 순서대로 삽입

        while(!q.isEmpty()) {
            int [] cur = q.poll();
            int node = cur[0];
            int income = cur[1];
            int a_time = cur[2];

            boolean isLeaf = true;
            for(int nxt : graph.get(node)) {
                if (visited[nxt]) continue;
                visited[nxt] = true;
                
                int b_time = bob_time[nxt];
                int newIncome = income;
                if (a_time + 1 < b_time || b_time == -1) { 
                    // bob이 방문하지 않았거나 앨리스보다 늦게 방문하는 경우
                    newIncome += amount[nxt];
                }

                else if (a_time + 1 == b_time) {
                    // 동시에 방문하는 경우는 reward / 2
                    newIncome += amount[nxt] / 2;
                }
                q.add(new int[]{nxt, newIncome, a_time + 1});
                isLeaf = false;
            }
            if (isLeaf) {
                max = Math.max(max, income);
            }
        }
    }
}

 

후기

문제가 생각보다 까다로워서 처음에 감을 잘 못잡았다. 특히, Bob의 시점에서 모든 경로 탐색을 진행하다보니 Alice쪽에서 계산을 할 때 잘못된 결과가 도출되었다. 

 

이전에 항상 DFS를 통해 그래프 탐색을 진행할 때는 void 타입으로 함수를 선언했는데 지금처럼 boolean 타입으로 선언해서 백트래킹을 합친 방식을 꼭 기억해야겠다. 안쓰는 경로는 -1로 초기화 하기!!