Find the diameter of the graph by breadth-first search (Python memory)
I registered with Qiita, but I haven't used it so much, so I'll try it.
Purpose of this article
・ Personal memo ・ I searched for a Python breadth-first search article before, but I couldn't find it, so I would like to publish it for similar beginners. ・ Someone may tell you how to write better if you write here
Conclusion
-The diameter of a graph that is concatenated and has no edge length can be found by breadth-first search (BFS). -The operation to retrieve the element from the top of the list is slow ・ However, using deque will improve it a little.
Problem to be solved and policy of answer
problem
ABC151 D - Maze Master
Solve this. (ABC's D question is sometimes given a graph question.) Please check the problem statement at the link.
Answer policy
Interpret it as a graph problem. The maze is represented by a connected graph by connecting the adjacent vertices on the top, bottom, left, and right with the square as the vertex. Therefore, this problem can be thought of as "the problem of finding the diameter of a graph that is concatenated and has no edge length." Here, the diameter is the maximum value of the distance between the vertices.
What is breadth-first search (BFS)?
For details, see other articles, but breadth-first search is an algorithm for finding a reachable location from a certain vertex (let's call it start).
This time I will apply this ** Find the maximum distance from the vertex (start) ** Perform the operation. First, prepare a list (edge) of edges connected to each vertex, and then enter the distance from start in the prepared list (distance) according to the following flowchart.
If you change the part "from the beginning" written in red in this flowchart to "from the end", it becomes a depth-first search (DFS). However, the diameter of the graph is not calculated by DFS.
Breadth-first search moves immediately to the reachable vertices, so there is no detour. Therefore, the shortest distance can be obtained. Of course, unless the sides have length.
Finally, do this for all vertices of the graph and print the largest of the obtained values and you're done.
H,W=[int(s) for s in input().split()]
maze=[input() for _ in range(H)]
edge=[set() for _ in range(H*W)]
n=0
numcount=0
for h in range(H):
for w in range(W):
if maze[h][w]=='#':
numcount+=1
n+=1
continue
if h>0 and maze[h-1][w]=='.':
edge[n].add(n-W)
if h<H-1 and maze[h+1][w]=='.':
edge[n].add(n+W)
if w>0 and maze[h][w-1]=='.':
edge[n].add(n-1)
if w<W-1 and maze[h][w+1]=='.':
edge[n].add(n+1)
n+=1
def dfs(start):
reach=[start]
distance=[-1 for _ in range(H*W)]
distance[n]=0
while reach:
_from=reach.pop(0)
for _to in edge[_from]:
if not(_to in reach) and distance[_to]==-1:
reach.append(_to)
distance[_to]=distance[_from]+1
return(max(distance))
n=0
ans=set()
for h in range(H):
for w in range(W):
if maze[h][w]=='.':
ans.add(dfs(n))
n+=1
print(max(ans))
You can now AC.
Getting to the top of the list is slow
Basically this is fine, but ... Python is pretty slow and will quickly become a TLE if you're not careful. It is better to reduce time-consuming operations as much as possible. For example, retrieving an element from the top of a list is very slow.
import time
list_1=[i for i in range(100000)]
list_2=[i for i in range(100000)]
#Extract elements from the beginning
start_1=time.time()
while list_1:
x=list_1.pop(0)
end_1=time.time()
#Extract elements from the end
start_2=time.time()
while list_2:
x=list_2.pop(-1)
end_2=time.time()
print('From the beginning:{}'.format(end_1-start_1))
#=>From the beginning: 1.4942412376403809
print('From the end:{}'.format(end_2-start_2))
#=>From the end: 0.014818668365478516
Even though I am doing the same operation, it takes about 100 times longer when I take out the element from the beginning. This time it was okay, but I think it's better to take measures when many similar operations continue.
use deque
When retrieving an element from the beginning of a list, a type called deque is useful. See here for details. collections --- container data type (Python 3.7.3 documentation)
Roughly speaking -Deque is fast when extracting elements from the beginning or end of an array ・ List is fast when taking out from the center It seems like that.
import time
from collections import deque
list_1=[i for i in range(100000)]
deq=deque([i for i in range(100000)])
#Start from the beginning with list
start_1=time.time()
while list_1:
x=list_1.pop(0)
end_1=time.time()
#Start from the beginning with deque
start_3=time.time()
while deq:
x=deq.popleft()
end_3=time.time()
print('list：{}'.format(end_1-start_1))
#=>list：1.4939298629760742
print('deque：{}'.format(end_3-start_3))
#=>deque：0.009586334228515625
It ended very early. The problem this time is that the length of the list is about 400, so it doesn't make much difference (rather slow), but the longer it is, the more likely it is to benefit. The answer using the deque is as follows.
from collections import deque
H,W=[int(s) for s in input().split()]
maze=[input() for _ in range(H)]
edge=[set() for _ in range(H*W)]
n=0
numcount=0
for h in range(H):
for w in range(W):
if maze[h][w]=='#':
numcount+=1
n+=1
continue
if h>0 and maze[h-1][w]=='.':
edge[n].add(n-W)
if h<H-1 and maze[h+1][w]=='.':
edge[n].add(n+W)
if w>0 and maze[h][w-1]=='.':
edge[n].add(n-1)
if w<W-1 and maze[h][w+1]=='.':
edge[n].add(n+1)
n+=1
def dfs(start):
reach=deque([start]) #This line changes
distance=[-1 for _ in range(H*W)]
distance[n]=0
while reach:
_from=reach.popleft() #This line changes
for _to in edge[_from]:
if not(_to in reach) and distance[_to]==-1:
reach.append(_to)
distance[_to]=distance[_from]+1
return(max(distance))
n=0
ans=set()
for h in range(H):
for w in range(W):
if maze[h][w]=='.':
ans.add(dfs(n))
n+=1
print(max(ans))
Summary
This time I learned about BFS. To be honest, I didn't realize that the diameter was calculated by BFS until I solved this problem. I would like to try solving other graph problems and post them when I have free time.
Recommended Posts