Solve with Python [100 selected past questions that beginners and intermediates should solve] (024 --027 Depth-first search)

1. Purpose

Solve 100 past questions that beginners and intermediates should solve in Python. The goal is to turn light blue by the time you finish solving everything.

This article is "024-027 Depth-first search".

2. Summary

It's easy to write in the article below, but it took me a long time to understand `BFS``` and `DFS. bfsWhendfs```の基本形をおさえるまでに、最初は解説を読んでもまったくわからず、理解するまでに1週間くらい（1日10時間以上悩むこWhenもあった）かかっています。

What I did to understand is that it is natural to read the commentary article, but try debugging the code that goes through AC and see how the data works line by line. I did it until I understood that I would check it. As for recursion, I actually wrote all the recursion calculations in my notebook.

Then, at some point, the data structures of `BFS``` and DFS``` were created in my head, and even if I didn't write anything in my notebook, I thought `` It was possible to move data like BFS, DFS```. Perhaps this moment will come depending on the individual, but I think that it will not come without a certain amount of thinking (trial?).

In addition, debug uses VS code debugger. Convenient. Like this.

3. Main story

024 --027 Depth-first search

024. ALDS_11_B --Depth-first search

Answer

N = int(input())
graph = [[] for _ in range(N+1)]
for _ in range(N):
    i, num, *nodes = map(int, input().split())
    graph[i] = nodes #Directed graph

go_time = [0] * (N+1)
back_time = [0] * (N+1)

def dfs(node, t):
    #Record of going
    t += 1
    go_time[node] = t
    for next_node in graph[node]:
        if go_time[next_node] == 0:
            t = dfs(next_node, t)
    #Record of return
    t += 1
    back_time[node] = t
    return t

t = 0
for node in range(1, N+1): #Try to start from all points
    if go_time[node] == 0:
        t = dfs(node, t)
    print(node, go_time[node], back_time[node])

First of all, receiving data is troublesome. Regarding how to receive graph information, the place where the length is variable is the last like ```i, num, * nodes = map (int, input (). Split ()) You can pass the rest to ``nodesby adding `` `* to * nodes ``. Reference-> Unpack tuples and lists in Python (expand and assign to multiple variables)

As you can see by submitting here, there may be some parts that you can not reach even if you start from 1 (I do not know where you can read this in the problem sentence ...), so try all points as candidates for starting is needed.

Both the recursive dfs written this time and the `dfs``` by `deque``` (in the case of python) need to remember the basic type first, and the explanation of the basic type Is quite difficult for me, so I will omit it. For the time being, I will learn this basic form and proceed at first.

025. AOJ 1160 --How many islands are there?

Answer

from collections import deque

def main(w, h, MAP, visited):
    count = 0
    #Try to start from all points
    for start_y in range(h):
        for start_x in range(w):
            if MAP[start_y][start_x] == 0: #Skip in the case of the sea
                continue
            if visited[start_y][start_x] != -1: #Skip the searched
                continue
            q = deque()
            q.append((start_y, start_x))
            visited[start_y][start_x] = 1
        
            while q:
                y, x = q.pop()

                for dy in range(-1, 2):
                    for dx in range(-1, 2):
                        moved_y = y + dy
                        moved_x = x + dx

                        if moved_y < 0 or h-1 < moved_y or moved_x < 0 or w-1 < moved_x: #Skip moving off the map
                            continue
                        if MAP[moved_y][moved_x] == 0: #Skip in the case of the sea
                            continue
                        if visited[moved_y][moved_x] != -1: #Skip the searched
                            continue
                        visited[moved_y][moved_x] = 1
                        q.append((moved_y, moved_x))
            
            count += 1 #One island after passing through while
    return count

if __name__ == "__main__":

    answer_list =[]
    while True:
        w, h = map(int, input().split())
        MAP = [list(map(int, input().split())) for _ in range(h)]
        visited = [[-1] * w for _ in range(h)]

        if w == 0 and h == 0:
            break
        
        answer = main(w, h, MAP, visited)
        answer_list.append(answer)

    for answer in answer_list:
        print(answer)

Personally, it's easier to write dfs by deck (decue?) Than recursion. This is also the basic form of `` `dfs``` (I think), so just write it as it is.

26. AtCoder Beginner Contest 138 D - Ki

Answer

from collections import deque
# -------------- [input] --------------
N, Q = map(int, input().split()) #N is the number of vertices, Q is the number of operations
graph = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

counts = [0] * (N+1)
for _ in range(Q):
    p, x  = map(int, input().split())
    counts[p] += x
visited = [-1] * (N+1)
# -------------- [Start from 1] --------------
q = deque()
q.append(1)
visited[1] = 1
# -------------- [DFS] --------------
while q:
    node = q.pop()

    next_nodes = graph[node]
    for next in next_nodes:
        if visited[next] != -1:
            continue
        q.append(next)
        visited[next] = 1
        counts[next] += counts[node] #Add parental score

print(*counts[1:])

This problem is AtCoder Beginner Contest 176 D --Wizard in Maze (Click here for my answer article → AtCoder ABC 176 Python (A ~ E) )) I felt it was a bit like that. This problem is easier, but ...

What is similar is `counts [next] + = counts [node] ``` in this part, `visited [moved_y] [moved_x] = visited [in ABC 176] y] [x] ``` Here.

The reason why I thought it was similar is when moving from the search target (let's call it ①) extracted by `q.pop ()` to the search target (let's call it ②) next to the search target ①. This is because the process of updating the information of ② using the information of ① is similar.

In normal (?) DFS``,` `BFS, the update of the information in ② above is often another list or just an increment, but the same list. I thought it would be difficult to come up with the method of updating with the information in the above unless I did it once. As long as you understand this point, the rest is not much different from the basic form of `` `BFS```.

027. JOI 2009 Qualifying 4-Thin Ice Crossing

Answer

import sys
sys.setrecursionlimit(10**9)

# -------------- [initial value] --------------
def dfs(count, start_y, start_x, visited):
    ans = count
    for dy, dx in moves:
        moved_y = start_y + dy
        moved_x = start_x + dx
        if moved_y < 0 or n-1 < moved_y or moved_x < 0 or m-1 < moved_x:
            continue
        if grid[moved_y][moved_x] == 0:
            continue
        if visited[moved_y][moved_x] != -1:
            continue
        visited[start_y][start_x] = 1
        ans = max(ans, dfs(count+1, moved_y, moved_x, visited)) #Get the maximum value that can be reached from the start point
        visited[start_y][start_x] = -1
    
    return ans


if __name__ == "__main__":
    # -------------- [input] --------------
    m = int(input()) #side
    n = int(input()) #Vertical
    grid = [list(map(int, input().split())) for _ in range(n)] # 1:Ice, 0:No ice
    moves = [(1, 0), (0, 1), (-1, 0), (0, -1)] #Up, down, left and right only
    visited = [[-1] * m for _ in range(n)]
    # -------------- [Try all points as a starting point] --------------
    answer = 0
    for start_y in range(n):
        for start_x in range(m):
            if grid[start_y][start_x] == 0:
                continue
            answer = max(answer, dfs(1, start_y, start_x, visited))

    print(answer)

sys.setrecursionlimit(10**9)You can pass without it, but I will leave it as a reminder.

 This is almost the same as the basic form, but the difference is

```python

ans = max(ans, dfs(count+1, moved_y, moved_x, visited)) #Get the maximum value that can be reached from the start point
visited[start_y][start_x] = -1

Only here. This will return the longest distance from each starting point.