Recherche de priorité de profondeur à l'aide de la pile en Python

introduction

J'ai récemment commencé la programmation compétitive et je suis accro à sa profondeur. Mais dans la programmation compétitive, si vous ne connaissez pas l'algorithme, vous serez complètement malade d'un certain niveau: déçu_relieved:

Donc, Directives pour améliorer AtCoder, un professionnel de la compétition enseigné par Red Coder [Édition intermédiaire: Visez Light Blue Coder! ] "[100 questions passées que les débutants et les intermédiaires devraient résoudre par champ](https://qiita.com/e869120/items/eb50fdaece12be418faa#2 -3-% E5% 88% 86% E9% 87% 8E% E5% 88% A5% E5% 88% 9D% E4% B8% AD% E7% B4% 9A% E8% 80% 85% E3% 81% 8C% E8% A7% A3% E3% 81% 8F% E3% 81% B9% E3% 81% 8D% E9% 81% 8E% E5% 8E% BB% E5% 95% 8F% E7% B2% BE% E9% 81% B8-100-% E5% 95% 8F) »se résout petit à petit ces jours-ci!

Recherche de priorité de profondeur

Ce qui m'intéressait cette fois, c'était la recherche de priorité en profondeur. Jusqu'à présent, il était implémenté de manière récursive, mais quand je l'ai recherché, il y a aussi un moyen d'utiliser la pile, donc je vais l'implémenter en utilisant la pile.

exemple

ALDS1_11_B, qui est écrit comme un problème de base, une recherche prioritaire approfondie de 100 questions passées Je vais le résoudre. Le point difficile de ce problème était de sortir l'heure de découverte et l'heure de fin de la recherche. (Parce que je suis encore un débutant ...)

1. Entrée

La première ligne a le nombre de sommets $ n $, la ligne $ n $ suivante, Étant donné le nombre de sommets $ u $, le nombre de sommets adjacents $ k $, et le nombre de sommets adjacents $ v_1 \ v_2 \ ... \ v_k $.

n = int(input())
ukv = [[0, 0, 0]] + [list(map(int, input().split())) for _ in range(n)]

Une liste de 0 est ajoutée en premier pour aligner les numéros de sommets et les numéros d'index. (Ce n'est pas absolument nécessaire.)

2. Variables requises

stack = []
visited = []
time = 0
d = [0] * (n + 1)
f = [0] * (n + 1)

Stack, qui agit comme une pile (Il semble que vous puissiez utiliser deque de collections. Cette fois, il est implémenté dans une liste.) Gardez une trace des pics que vous avez déjà visités "Temps" représentant le temps Liste des heures de pointe de découverte d Liste des temps de complétion des sommets f («D» et «f» sont également définis sur «n + 1» car ils ont le même numéro d'index.)

3. Rechercher une partie

while stack:
    s = stack[-1]             # (1)Top à explorer
    k = ukv[s][1]             # (2)Nombre de sommets adjacents de s
    if k == 0:                # (6)Puisqu'il n'y a pas de sommets adjacents de s
        stack.pop()           #Retirer les s de la pile
        time += 1
        f[s] = time           # (7)Heure à laquelle la recherche de s a été terminée
    else:
        v = ukv[s].pop(2)     # (3)Le sommet avec le plus petit nombre adjacent à s
        ukv[s][1] -= 1        # (4)Réduisez le nombre de sommets adjacents de s
        if v not in visited:
            stack.append(v)
            visited.append(v)
            time += 1
            d[v] = time       # (5)Le moment où v a été découvert

Le but n'est pas de pop () from stack lors de la définition de la variable s. Au début, j'ai essayé de gérer le temps de découverte et le temps d'achèvement dans différentes listes et je me suis perdu. Le «s» est supprimé de la «pile» lorsqu'il s'agit de (6) ci-dessus. Le moment où la recherche de «s» est terminée est quand il trouve tous les sommets accessibles à partir de «s» et revient à «s». Par conséquent, (4) réduit le nombre de sommets adjacents.

Maintenant, si vous mettez «1» dans «pile» ou «visité», vous pouvez effacer l'exemple d'entrée. Cependant, si je le soumets tel quel, j'obtiendrai WA </ font> du cas de test 1 :: scream:

La recherche continue à partir du point de départ d'origine jusqu'à ce que tous les sommets atteignables soient trouvés, et s'il reste des sommets non découverts, la recherche continue avec celui avec le plus petit nombre comme nouveau point de départ.

Je l'ai négligé.

4. Apex non découvert

Ce problème est d'environ $ 1 \ leq n \ leq 100 $, donc je l'ai traité dans une boucle de 1 à n + 1.

for i in range(1, n + 1):
    if i not in visited:
        stack.append(i)
        visited.append(i)
        time += 1
        d[i] = time

Si ʻi n'est pas dans visité`, c'est un sommet non découvert et la recherche continue.

5. Exemple de réponse

n = int(input())
ukv = [[0, 0, 0]] + [list(map(int, input().split())) for _ in range(n)]

stack = []
visited = []
time = 0
d = [0] * (n + 1)
f = [0] * (n + 1)
for i in range(1, n + 1):
    if i not in visited:
        stack.append(i)
        visited.append(i)
        time += 1
        d[i] = time

        while stack:
            s = stack[-1]
            k = ukv[s][1]
            if k == 0:
                stack.pop()
                time += 1
                f[s] = time
            else:
                ukv[s][1] -= 1
                v = ukv[s].pop(2)
                if v not in visited:
                    stack.append(v)
                    visited.append(v)
                    time += 1
                    d[v] = time

for i in range(1, n + 1):
    print(i, d[i], f[i])

J'ai pu AC </ font> sans aucun problème. C'est peut-être beaucoup de code inutile, mais je pense personnellement que c'était facile à comprendre: thumbsup: Si vous avez des améliorations de code, veuillez laisser un commentaire! !!

en conclusion

Cette question était destinée à la pratique de la recherche en profondeur d'abord, comme le titre l'indique Depth First Search. C'est la base des bases!

Personnellement, je pense que la recherche de priorité en profondeur est facile à comprendre lors de la mise en œuvre à l'aide d'une pile. Bien entendu, selon le problème, il est nécessaire de l'utiliser correctement comme récursif.

La programmation compétitive a différentes approches pour un problème, donc l'augmentation des retraits est essentielle. J'aimerais pouvoir continuer à l'augmenter petit à petit ...

Au fait, je suis une nana qui commence tout juste à participer au concours: hatched_chick: https://atcoder.jp/users/ajim

Recommended Posts