본문으로 건너뛰기

1857 - Largest Color Value in a Directed Graph

info

풀이 키워드​

스포주의

정렬 DP


풀이 코드​

info
  • 메모리: 121900 KB
  • 시간: 75 ms
class Solution {
    public int largestPathValue(String colors, int[][] edges) {
        final int n = colors.length();
        List<Integer>[] adj = new ArrayList[n];
        for (int i = 0; i < n; ++i) adj[i] = new ArrayList<>();
        int[] indegree = new int[n];

        // init adj, indegree
        for (int[] e : edges) {
            adj[e[0]].add(e[1]);
            ++indegree[e[1]];
        }

        // init topo sort queue
        Deque<Integer> q = new ArrayDeque<>();
        for (int i = 0; i < n; ++i)
            if (indegree[i] == 0) q.add(i);

        // topo sort w/ dp
        int ans = 0;
        int visited = 0; // if DAG, visited should end w/ n
        int dp[][] = new int[n][26]; // node index, color
        while (!q.isEmpty()) {
            int u = q.poll();
            visited += 1;
            int cdx = colors.charAt(u) - 'a';
            ++dp[u][cdx]; // 1. count color
            ans = Math.max(ans, dp[u][cdx]); // 2. update maximum sum

            // search next node
            for (int v : adj[u]) {
                for (int c = 0; c < 26; ++c)
                    dp[v][c] = Math.max(dp[u][c], dp[v][c]); // 3. copy color cnt cache
                if (--indegree[v] == 0) q.add(v); // 4. remove incoming edge
            }
        }

        return visited == n ? ans : -1;
    }
}

풀이 해설​

위상정렬 로직 내에 DP를 끼워넣어서 푸는 문제이다.

시간복잡도는 T(n+m+26⋅n)=O(n+m)T(n + m + 26 \cdot n) = O(n + m) 이다.


DAG & Topology sort​

위상정렬은 선행 -> 후행 순으로 노드를 정렬하는 알고리즘으로, 쉽게 생각해서 갑을병정 순으로 정렬해준다.

위상정렬이 제대로 작동하려면 DAG(Directed Acyclic Graph)여야 한다.

✅ Directed Graph​

무엇이 갑이고 무엇이 을인지 노드 간의 계층 관계를 간선의 방향이 결정해준다.

✅ Acyclic Graph​

사이클이 있는 방향 그래프는 위상정렬에게 있어 콩가루 그래프이다.

그래서 사이클이 없어야 한다.

위상정렬을 수행할 수 없는 그래프
삼성전자 ➡ 1차 하청
  ⬆(?)      ⬇
3차 하청 ⬅ 2차 하청

정렬 수행 방식​

자주 쓰이는 큐 방식 기준으로 설명한다.

1️⃣ 인접리스트 만들면서 해당 노드의 진입 차수를 별도의 배열에 기록

for (int[] e : edges) {
    adj[e[0]].add(e[1]);
    ++indegree[e[1]];
}

2️⃣ 진입 차수가 0인 노드를 큐에 넣기

따라서 그래프가 울릉도 독도 제주도마냥 서로 분리되어있어도 상관없다.

어차피 각 분리된 그래프별로 indegree가 0인 노드를 큐에 넣기 때문이다.

Deque<Integer> q = new ArrayDeque<>();
for (int i = 0; i < n; ++i)
    if (indegree[i] == 0) q.add(i);

3️⃣ 큐에서 노드 꺼내고 연결된 edge 제거하기

u -> v 일때 해당 연결관계를 제거하는데 이는 곧 v의 진입 차수가 1 줄어드는 것과 같다.

제거 후 v의 진입 차수가 0이 되었다면 v를 큐에 넣는다.

while (!q.isEmpty()) {
    int u = q.poll();

    // search next node
    for (int v : adj[u]) {
        if (--indegree[v] == 0) q.add(v);
    }
}

사이클 유무 판별​

다음과 같은 有사이클 방향 그래프가 있다고 하자.

A -> B -> C
     ↑ ↙
     D -> E

이런 형태의 그래프에서 indegree는 다음과 같다.

ABCDE
02111

그렇다면 맨 처음 큐에 들어가는 노드는 A일 것이다.

A를 꺼내서 인접한 B와의 연결을 끊고, B의 진입 차수를 1 감소시킨다.

그럼 indegree는 이렇게 된다.

ABCDE
01111

그리고 B의 진입 차수는 여전히 0보다 크기 때문에 큐에 넣을 수 없다.

결국 A의 인접 노드 순회가 종료되고 큐는 isEmpty()에 걸려서 모든 노드를 순회하지 못한 채 while 문이 종료된다.

따라서 큐에서 노드를 꺼낼때마다 방문한 노드를 카운팅하고 (visited)

마지막에 해당 카운터가 총 노드 개수와 같은지(=모든 노드를 순회했는지) 체크해서 사이클 여부를 판단할 수 있다.


DP 정의​

u와 인접한 노드인 v로 탐색이 넘어간다고 했을 때, v는 u까지의 color 정보를 알고 있어야 한다.

그렇다면 dp[v][c] = dp[u][c] 인가? 물론 아니다.

왜 아닐까? 그건, u에서 v로 가기 전에

이미 다른 경로로 v에 도달했었을 수도 있기 때문이다.

따라서 상향식 기준으로 아래와 같은 코드가 된다.

dp[v][c] = Math.max(dp[u][c], dp[v][c]);

메모​

  • 다른 알고리즘 기법이랑 섞어서 푸는 부분이 유익함