백준 31110번: Autobiography [Python]

작성일 | In
골드 III 골드 III

문제

Autobiography

정점에 b 또는 o라는 알파벳이 매겨져 있는 어떤 무방향 그래프에서 정점 4개로 이루어진 경로 중 정점의 알파벳이 순서대로 bobo가 되는 것의 개수를 구하는 문제입니다.

풀이

모든 정점에 대해 4만큼의 깊이로 백트래킹을 하면 시간 복잡도가 최악의 경우 $O(n^4)$가 되므로 시간 초과를 받습니다.

bobo에서 두 번째 o가 될 수 있는 정점과, 세 번째 b가 될 수 있는 정점이 인접해 있으면 그 둘을 중심으로 하는 bobo 경로의 개수를 빠르게 계산할 수 있습니다.

각 정점 $i$에 대해 인접한 정점 중 자기 자신과 알파벳이 다른 것의 개수를 셉니다. 이를 $c_i$라 합시다.

정점 중 알파벳이 o이고 서로 알파벳이 다른 인접한 정점의 개수가 $2$ 이상인 정점 $v$를 찾습니다. 마찬가지로 $v$와 연결된 정점 중 알파벳이 b이고 서로 알파벳이 다른 인접한 정점의 개수가 $2$ 이상인 정점 $w$를 찾습니다.

경로 $u-v-w-x$에서 $u$로 가능한 정점은 $c_v$개에서 $w$를 제외한 $c_v - 1$개입니다. 마찬가지로 $x$로 가능한 정점의 개수도 $c_w - 1$개입니다.

따라서 $v-w$를 중심으로 하는 bobo 경로의 개수는 $(c_v - 1)(c_w - 1)$개입니다.

각 정점에서 인접한 정점들만 보면 계산할 수 있으므로 시간 복잡도는 $O(n + m)$입니다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
def solve():
    n, m = map(int, input().split())
    c = "#" + input()

    adj = [[] for _ in range(n + 1)]
    for _ in range(m):
        a, b = map(int, input().split())
        adj[a].append(b)
        adj[b].append(a)

    counter_count = [0] * (n + 1)
    for i in range(1, n + 1):
        for j in adj[i]:
            if c[i] != c[j]:
                counter_count[i] += 1

    answer = 0
    for i in range(1, n + 1):
        if c[i] != "o" or counter_count[i] < 2:
            continue

        for j in adj[i]:
            if c[j] != "b" or counter_count[j] < 2:
                continue

            answer += (counter_count[i] - 1) * (counter_count[j] - 1)

    print(answer)


def main():
    try:
        while True:
            solve()
    except EOFError:
        pass


main()

백준 31110번: Autobiography [Python]