Bfs
layout: post title: BFS template and practice questions category: Data structure & Algorithms tags:
-
Data structure & Algorithms
Intro
Use queue for BFS to find the shortest something and when weight to travel nodes is constant like one. Dijkstra is also finding the shortest something but when weights are not constant for each node.
Precautions
Btw if input is given like [“X591X”,”X1X5X”,”X231X”, “1XXX1”] and we should convert it to 2d graph representation like
def convert_to_graph(lst):
graph = []
for row in lst:
graph.append(list(row))
return graph
Also really important for the boundary check of 2x2 graph.
The problem lies in the condition next_x >= len(graph) when checking the bounds for next_x in the BFS loop. It should be next_x >= len(graph[0]) since the length of each row in graph represents the number of columns.
Practice questions
그림
My intitial wrong code. As you can see, it is really messy and I dont really know the exact way to implement BFS. Actually in a simple grid question like this, instead of creating a separate visited 2d list, you can instead just mark the board graph itself by making the value 0. We do bfs on grid that is 1 anyways so when we are doing with bfs, just mark that as 0 and future bfs searches will not search that grid anymore.
from collections import deque
n, m = map(int, input().split())
graph = []
for i in range(n):
graph.append(list(map(int, input().split())))
visited= [[False for _ in range(m)] for _ in range(n)]
count = 0
area = 0
moves = [[1,0],[-1,0],[0,1],[0,-1]]
def bfs(graph,visited,queue):
area=0
while queue:
curr_x,curr_y,curr_area = queue.popleft()
area = max(area,curr_area)
for move in moves:
next_x,next_y = move[0]+curr_x,move[1]+curr_y
if next_x<0 or next_x>=n or next_y<0 or next_y>=m:
continue
if graph[next_x][next_y]==0:
continue
if graph[next_x][next_y]==1:
if not visited[next_x][next_y]:
queue.append((next_x,next_y,curr_area+1))
visited[next_x][next_y] = True
# graph[next_x][next_y]=0
return area
for i in range(len(graph)):
for j in range(len(graph[0])):
if graph[i][j]==1:
queue = deque()
queue.append((i,j,1))
visited[i][j]=True
# graph[i][j]=0
hola = bfs(graph,visited,queue)
area = max(area,hola)
count+=1
print(count)
print(area)
But you can still use visited 2d list anyways like this Correct code:
from collections import deque
n, m = map(int, input().split())
graph = []
for i in range(n):
graph.append(list(map(int, input().split())))
visited = [[False for _ in range(m)] for _ in range(n)]
count = 0
area = 0
moves = [[1, 0], [-1, 0], [0, 1], [0, -1]]
def bfs(graph, visited, a, b):
queue = deque()
queue.append((a, b))
visited[a][b] = True
count = 1
while queue:
x, y = queue.popleft()
for move in moves:
nx = x + move[0]
ny = y + move[1]
if nx < 0 or nx >= n or ny < 0 or ny >= m:
continue
if graph[nx][ny] == 1 and not visited[nx][ny]:
queue.append((nx, ny))
visited[nx][ny] = True
count += 1
return count
paint = []
for i in range(n):
for j in range(m):
if graph[i][j] == 1 and not visited[i][j]:
paint.append(bfs(graph, visited, i, j))
if len(paint) == 0:
print(len(paint))
print(0)
else:
print(len(paint))
print(max(paint))
Without a separate 2d list and marking grid as 0:
from collections import deque
n, m = map(int, input().split())
graph = []
for i in range(n):
graph.append(list(map(int, input().split())))
count = 0
area = 0
moves = [[1, 0], [-1, 0], [0, 1], [0, -1]]
def bfs(graph, a, b):
queue = deque()
queue.append((a, b))
graph[a][b] = 0
count = 1
while queue:
x, y = queue.popleft()
for move in moves:
nx = x + move[0]
ny = y + move[1]
if nx < 0 or nx >= n or ny < 0 or ny >= m:
continue
if graph[nx][ny] == 1:
queue.append((nx, ny))
graph[nx][ny] = 0 # Mark the cell as visited by setting it to 0
count += 1
return count
paint = []
for i in range(n):
for j in range(m):
if graph[i][j] == 1:
paint.append(bfs(graph, i, j))
if len(paint) == 0:
print(len(paint))
print(0)
else:
print(len(paint))
print(max(paint))
My STILL WRONG CODE:
from collections import deque
n, m = map(int, input().split())
graph = []
for i in range(n):
graph.append(list(map(int, input().split())))
visited= [[False for _ in range(m)] for _ in range(n)]
count = 0
area = 0
moves = [[1,0],[-1,0],[0,1],[0,-1]]
def bfs(graph,i,j):
queue = deque()
queue.append((i,j))
# omitting this line caused the error!
visited[i][j]=True
area = 1
while queue:
curr_x,curr_y= queue.popleft()
for move in moves:
next_x,next_y = move[0]+curr_x,move[1]+curr_y
if next_x<0 or next_x>=n or next_y<0 or next_y>=m:
continue
# this can be omitted too for simplicity
# if graph[next_x][next_y]==0:
# continue
if graph[next_x][next_y]==1:
if not visited[next_x][next_y]:
queue.append((next_x,next_y))
visited[next_x][next_y] = True
area +=1
# graph[next_x][next_y]=0
return area
for i in range(len(graph)):
for j in range(len(graph[0])):
if graph[i][j]==1 and not visited[i][j]:
hola = bfs(graph,i,j)
area = max(area,hola)
count+=1
print(count)
print(area)
Oh!! Turns out i wasnt marking the start of bfs search as visited! So in my bfs function, at the very starting point, i should have marked it as visited!! Oops!
부대복귀
https://school.programmers.co.kr/learn/courses/30/lessons/132266
Let’s start with a typical DFS question that picks a starting point and spreads out in 4 directions grid to search for end point.
from collections import deque
def solution(n, roads, sources, destination):
# or just graph = defaultdict(list)
graph = [[] for _ in range(n+1)]
for road in roads:
start,end=road
graph[start].append(end)
graph[end].append(start)
answer = []
for source in sources:
answer.append(bfs(graph,destination,n,source))
return answer
def bfs(graph,destination,n,source):
queue = deque()
queue.append((source,0))
visited = [False for _ in range(n+1)]
visited[source]=True
while queue:
cur_node,cur_cost = queue.popleft()
# you dont need this line here, do it when you are appending it to queue
# visited[cur_node]=True
if cur_node == destination:
return cur_cost
for next_node in graph[cur_node]:
if not visited[next_node]:
# do it here
visited[next_node]=True
queue.append((next_node,cur_cost+1))
return -1
My bfs is correct but it has runtime error for some large cases.
So how about instead of calculating distance from starting source to destination, we do the other way around? My initial code will calculate distance to destination multiple times if starting sources take the same shortest route to destination. But if we do vice versa, we just calculate the distance from destination to starting sources once.
Again my wrong code
from collections import deque
def solution(n, roads, sources, destination):
graph = [[] for _ in range(n+1)]
for road in roads:
start,end=road
graph[start].append(end)
graph[end].append(start)
distance = [-1 for _ in range(n+1)]
distance[destination]=0
ans = bfs(graph,destination,n,distance)
return [ans[i] for i in sources]
def bfs(graph,destination,n,distance):
queue = deque()
queue.append((destination,0))
while queue:
cur_node,cur_cost = queue.popleft()
# u dont need this line, mark it when you are appending it to queue
# distance[cur_node]=cur_cost
for next_node in graph[cur_node]:
if distance[next_node]== -1:
queue.append((next_node,cur_cost+1))
# need this line
distance[next_node] = cur_cost + 1
return distance
This 1 line makes the difference. I thought you don’t have to update distance of next_node’s cost because we do that in the queue via distance[cur_node]=cur_cost.
거리두기 확인하기
https://school.programmers.co.kr/learn/courses/30/lessons/81302
This question needs BFS search multiple times on the same board itself. I didn’t know how to get the value of BFS search result and if abnormal, append to answer list. To do this, we can use flag. We first set flag as True or value 1 and when BFS search comes out abnormal, we can set flag as False based on that BFS search result condition.
Also, it is smart to optimise the movement loop like instead of
movements = [[1,0],[-1,0],[0,-1],[0,1]]
We can use a dictionary like
dic = {0: [0, -1], 1:[-1, 0], 2:[0, 1], 3:[1, 0]}
Also be very careful with difference on number 0 and alphabet O. I put it like if place at dx,dy =’0’ but it should have been alphabet O.
My attempt, which is wrong
for i in range(4):
nx = x + dic[i][0]
ny = y + dic[i][1]
nd = d + 1
# if dx<0 or dy <0 or dx>=5 or dy >=5:
# continue
if 0 <= dx < 5 and 0 <= dy < 5 and not visited[dx][dy]:
visited[dx][dy]= True
if place[dx][dy]=='P':
if dist<=2:
return 0
elif place[dx][dy] =='0':
if dist==1:
queue.append([dx,dy,dist])
Correct
from collections import deque
ans=[]
def bfs(place,pos):
queue = deque([pos])
visited = [[False for _ in range(5)] for _ in range(5)]
dic = {0: [0, -1], 1:[-1, 0], 2:[0, 1], 3:[1, 0]}
while queue:
x,y,d = queue.popleft()
visited[x][y] = True
for i in range(4):
dx = x + dic[i][0]
dy = y + dic[i][1]
dist = d+1
if dx<0 or dy <0 or dx>=5 or dy >=5:
continue
if not visited[dx][dy]:
visited[dx][dy]= True
if place[dx][dy]=='P' and dist<=2:
return 0
elif place[dx][dy] =='O' and dist<=1:
queue.append([dx,dy,dist])
return 1
def solution(places):
# global ans
for place in places:
flag =1
for row in range(len(places[0])):
for col in range(len(places)):
if place[row][col]=='P':
val = bfs(place,[row,col,0])
if val == False:
flag =0
ans.append(1 if flag==1 else 0)
return ans
경주로 건설
https://school.programmers.co.kr/learn/courses/30/lessons/67259 In my queue, the parameters that I store will lead to wrong answer. I store the previous direction as well
My solution
from collections import deque
def solution(board):
visited= [[False for _ in range(len(board[0]))] for _ in range(len(board))]
length = len(board)
queue = deque()
# queue.append((0, 0, 0, dir))
answer=[]
queue.append((0, 0, 1, 0, 0))
queue.append((0,0,0,1,0))
visited[0][0] = True
while queue:
moves = [[1,0],[-1,0],[0,-1],[0,1]]
x,y,prevX,prevY, cost = queue.popleft()
for move in moves:
dx,dy= x+move[0],y+move[1]
if dx<0 or dx>=len(board[0]) or dy<0 or dy>=length or board[dx][dy]==1:
continue
if dx == len(board[0]) - 1 and dy == length - 1:
answer.append(cost)
cost += check_direction(move[0],move[1],prevX,prevY,cost)
print(cost)
if not visited[dx][dy]:
visited[dx][dy]= True
queue.append((dx,dy,move[0],move[1],cost))
print((dx,dy,move[0],move[1],cost))
return min(answer)
def check_direction(nextX,nextY,prevX,prevY,cost):
if prevX == nextX and prevY==nextY:
cost+=100
else:
cost+=500
return cost
solution([[0,0,0],[0,0,0],[0,0,0]])
But this will that when bfs starts on starting point 0,0, we can move both directions - right and down. So in this case, we use a little trick that marks a custom direction just for this edge case. We mark the direction as integer 5.
I tried fixing code like this but still didnt work. I think its cuz this visited is not allowing other paths stored in my queue to explore properly. Also my cost is mega huge idk why
from collections import deque
def solution(board):
visited= [[False for _ in range(len(board[0]))] for _ in range(len(board))]
length = len(board)
queue = deque()
answer=[]
# current x, current y, direction, cost
queue.append((0, 0, 5, 0))
visited[0][0] = True
while queue:
moves = [[1,0],[-1,0],[0,-1],[0,1]]
x,y,prevDirection, cost = queue.popleft()
for i in range(len(moves)):
dx,dy= x+moves[i][0],y+moves[i][1]
if dx<0 or dx>=len(board[0]) or dy<0 or dy>=length or board[dx][dy]==1:
continue
if dx == len(board[0]) - 1 and dy == length - 1:
answer.append(cost)
cost += check_direction(i,prevDirection,cost)
print(cost)
if not visited[dx][dy]:
visited[dx][dy]= True
queue.append((dx,dy,i,cost))
print((dx,dy,i,cost))
return min(answer)
def check_direction(currentDirection, prevDirection,cost):
if prevDirection ==5:
cost+=100
elif currentDirection==prevDirection:
cost+=100
else:
cost+=500
return cost
solution([[0,0,0],[0,0,0],[0,0,0]])
But official solution is here. We actually dont create a visited list because other paths stored in queue will not be able to visit the already-visited points by another path that has been processed earlier. So instead, we allow possibility that other paths will go back and forth and back and forth because there is no mark of visited points. But we create a price 2d list that record the smallest price of any path that visits that point.
Ok my explanation above is wrong (June 11th fix) So even though there is no visited list, we have this condition that stop unnecessary paths from being added to our queue. The condition is if the point that we are visiting has a cost that is recorded and is higher than our current cost to visit it, we override that value. So if our current cost is higher, that means there is a path that has lower cost that has been already added to our queue. So, we don’t visit that point and try other path.
Like this:
if nc <= price[nx][ny]:
price[nx][ny] = nc
queue.append((nx, ny, nc, i))
from collections import deque
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
def bfs(board):
n = len(board)
price = [[int(1e9)] * n for _ in range(n)]
price[0][0] = 0
queue = deque()
queue.append((0, 0, 0, 5)) # (시작X, 시작Y, 시작Cost, 시작방향)
while queue:
x, y, c, z = queue.popleft()
if x == n - 1 and y == n - 1:
continue
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
nz = i
if nx < 0 or nx >= n or ny < 0 or ny >= n:
continue
if board[nx][ny] == 1:
continue
if z==5:
nc = c + 100
elif nz == z:
nc = c + 100
else:
nc = c + 600
if nc <= price[nx][ny]:
price[nx][ny] = nc
queue.append((nx, ny, nc, i))
return price[-1][-1]
def solution(board):
n = len(board)
answer = bfs(board)
return answer
Actually this is Dijskstra question
미로 탈출
https://school.programmers.co.kr/learn/courses/30/lessons/159993
My wrong code
from collections import deque
def solution(maps):
# why is test cas3 -1??
# cuz my bfs search marks visited as True for an answerpath that needs to be visited later, but cannot be visited cuz it is already visited
row = len(maps)
col = len(maps[0])
graph = [['1' for _ in range(col)] for _ in range(row)]
for i in range(len(maps)):
for j in range(len(maps[0])):
if maps[i][j]=='S':
start_pos = (i,j)
elif maps[i][j]=='L':
lever_pos = (i,j)
elif maps[i][j] == 'E':
end_pos = (i,j)
graph[i][j]=maps[i][j]
visited = [[False for _ in range(col)] for _ in range(row)]
visited[start_pos[0]][start_pos[1]] = True
moves = [[1,0],[-1,0],[0,-1],[0,1]]
queue = deque()
queue.append(((start_pos[0],start_pos[1]),0,False))
while queue:
cur_pos, cur_cost, flag = queue.popleft()
cur_x, cur_y = cur_pos[0], cur_pos[1]
if cur_x == end_pos[0] and cur_y == end_pos[1] and flag ==True:
return cur_cost
# if cur_x == lever_pos[0] and cur_y == lever_pos[1]:
# flag = True
for move in moves:
next_x, next_y = cur_x +move[0], cur_y+move[1]
if next_x<0 or next_x >=row or next_y <0 or next_y >=col:
continue
if graph[next_x][next_y] =='X':
continue
if next_x == lever_pos[0] and next_y == lever_pos[1]:
flag = True
if not visited[next_x][next_y]:
queue.append(((next_x,next_y),cur_cost+1,flag))
visited[next_x][next_y]=True
return -1
Instead, you need to do 2 bfs search - 1 from start to lever and 1 from lever to end point. Another important note is that I don’t pass visited list as parameter to my bfs function because visited list needs to be renewed for each bfs search. So visited list needs to be freshly instantiated within the function, not passes as a parameter because we are gonna reuse it over and over again.
from collections import deque
moves = [[1,0],[-1,0],[0,-1],[0,1]]
def solution(maps):
# why is test cas3 -1??
# cuz my bfs search marks visited as True for an answerpath that needs to be visited later, but cannot be visited cuz it is already visited
row = len(maps)
col = len(maps[0])
graph = [['1' for _ in range(col)] for _ in range(row)]
for i in range(len(maps)):
for j in range(len(maps[0])):
if maps[i][j]=='S':
start_pos = (i,j)
elif maps[i][j]=='L':
lever_pos = (i,j)
elif maps[i][j] == 'E':
end_pos = (i,j)
graph[i][j]=maps[i][j]
val1 = bfs(start_pos,lever_pos,graph,maps)
val2 = bfs(lever_pos,end_pos,graph,maps)
return val1+val2 if val1>0 and val2>0 else -1
def bfs(start_pos,end_pos,graph,maps):
row = len(maps)
col = len(maps[0])
queue = deque()
queue.append(((start_pos[0],start_pos[1]),0))
visited = [[False for _ in range(col)] for _ in range(row)]
visited[start_pos[0]][start_pos[1]] = True
while queue:
cur_pos, cur_cost = queue.popleft()
cur_x, cur_y = cur_pos[0], cur_pos[1]
if cur_x == end_pos[0] and cur_y == end_pos[1]:
return cur_cost
# if cur_x == lever_pos[0] and cur_y == lever_pos[1]:
# flag = True
for move in moves:
next_x, next_y = cur_x +move[0], cur_y+move[1]
if next_x<0 or next_x >=row or next_y <0 or next_y >=col:
continue
if graph[next_x][next_y] =='X':
continue
if not visited[next_x][next_y]:
queue.append(((next_x,next_y),cur_cost+1))
visited[next_x][next_y]=True
return -1
단어 변환
https://school.programmers.co.kr/learn/courses/30/lessons/43163
First, my wrong code. While I was correctly checking for every word in words list and if there is just one char difference, I add that new_word and curr_count+1 to my queue. However, my code is going to infinite recursion. That is strange. I just wanted word in words list that matches this condition to be added to my queue and that was it.
from collections import deque
def solution(begin, target, words):
queue = deque()
queue.append((begin, 0))
count = bfs(queue, target, words)
print(count)
return count
def bfs(queue, target, words):
while queue:
curr_word, curr_count = queue.popleft()
if curr_word == target:
return curr_count
for word in words:
match_count = 0
for i in range(len(word)):
if word[i] != curr_word[i]:
match_count += 1
if match_count == 1:
queue.append((word, curr_count + 1))
# Remove the visited word from the list to avoid revisiting
# words.remove(word)
return 0
But look at my implementation.
for word in words:
While I was looping through word in words, I am not adding a stop condition like a visited list to mark the current word as “visited”. So it goes on an infinite loop on the same word over and over and over again.
So if we want to avoid revisiting the same node again and again, we can remove current word from our words list by adding
if match_count == 1:
queue.append((word, curr_count + 1))
# Remove the visited word from the list to avoid revisiting
words.remove(word)
But ideally we do not want to change or modify the input parameter of words list so we have 2 alternate ways - make visited list or loop through word by index.
First with a visited list
# in your solution as we dont want to instantiate a new one when bfs is executed
# want to keep using this visited list for all queue elements
visited = [] # List to track visited words
# in your bfs
for word in words:
if word not in visited: # Check if the word is not visited
match_count = 0
for i in range(len(word)):
if word[i] != curr_word[i]:
match_count += 1
if match_count == 1:
queue.append((word, curr_count + 1))
visited.append(word)
Secondly you can really easily loop through like
for i in range(len(words)):
for i in range(len(words[i]))
This ensures that we don’t revisit the element in the list again cuz the index keeps increasing and we get a new word each time.
여행경로
https://school.programmers.co.kr/learn/courses/30/lessons/43164
MY initial code i think does not backtrack like if there are tickets ICN-AAA, ICN-BBB, BBB-ICN, my route should not finish at ICN-AAA just because it is lexicogrphically smaller. Instead it should be ICN - BBB - ICN -AAA.
[Fix 28th June] Actually that is not the issue with my code. My code does not account for duplicate tickets given as parameter. Continued on next paragraph
This does not work for duplicate keys
from collections import defaultdict, deque
def solution(tickets):
graph = defaultdict(list)
for ticket in tickets:
graph[ticket[0]].append(ticket[1])
queue = deque()
ans = []
queue.append(('ICN', ['ICN'], set()))
ans.append(bfs(queue, graph, tickets))
print(sorted(ans)[0])
return sorted(ans)[0]
def bfs(queue, graph, tickets):
while queue:
cur_node, curr_path, used = queue.popleft()
if len(used) == len(tickets):
return curr_path
for next_node in sorted(graph[cur_node]):
if (cur_node, next_node) not in used:
next_used = used.copy()
next_used.add((cur_node, next_node))
queue.append((next_node, curr_path + [next_node], next_used))
Since I am using a set I cannot use a duplicate ticket and store it in my set as visited.
solution([["ICN", "AAA"], ["ICN", "CCC"], ["CCC", "DDD"], ["AAA", "BBB"], ["AAA", "BBB"], ["DDD", "ICN"], ["BBB", "AAA"]])
# ans should be
["ICN", "CCC", "DDD", "ICN", "AAA", "BBB", "AAA", "BBB"]
or you can use stack like
from collections import deque, defaultdict
def solution(tickets):
ans = []
graph = defaultdict(list)
path = []
for ticket in tickets:
graph[ticket[0]].append(ticket[1])
for key in graph.keys():
graph[key].sort()
stack = deque()
stack.append('ICN')
while stack:
from_city = stack[-1]
if from_city not in graph or len(graph[from_city])==0:
path.append(stack.pop())
else:
stack.append(graph[from_city].pop(0))
return path[::-1]
가장 먼 노드
https://school.programmers.co.kr/learn/courses/30/lessons/49189
previous wrong code
from collections import defaultdict, deque, Counter
def solution(n, edge):
visited = [False for _ in range(n+1)]
temp = defaultdict(list)
for start, end in edge:
temp[start].append(end)
temp[end].append(start)
queue = deque()
queue.append((1, 0))
ans = bfs(queue, visited, temp)
distances = [distance for node, distance in ans]
counter = Counter(distances)
highest_distance = max(counter.keys())
return counter[highest_distance]
def bfs(queue, visited, temp):
ans = []
while queue:
cur_node, cur_dist = queue.popleft()
ans.append([cur_node, cur_dist])
visited[cur_node] = True
for next_node in temp[cur_node]:
if not visited[next_node]:
queue.append((next_node, cur_dist + 1))
return ans
Oh the error was that I was marking visited node in my while loop like visited[cur_node] in my while loop but it should be marked at the point when it is added to queue like visited[next_node] = True.
But why?
It should be marked as visited at the point when it is enqueued because when I debugged, if we dont do that then it will marked as visited only when it is dequeed. But the problem is that the other paths may explore that node which should have been marked as visited but hasnt been popped off and thus is wrongly marked as not visited.
So fix that and I got
from collections import defaultdict, deque, Counter
def solution(n, edge):
visited = [False for _ in range(n+1)]
temp = defaultdict(list)
for start, end in edge:
temp[start].append(end)
temp[end].append(start)
queue = deque()
queue.append((1, 0))
visited[1]=True
ans = bfs(queue, visited, temp)
# print(ans)
distances = [distance for node, distance in ans]
counter = Counter(distances)
highest_distance = max(counter.keys())
# print(counter[highest_distance])
return counter[highest_distance]
def bfs(queue, visited, temp):
ans = []
while queue:
cur_node, cur_dist = queue.popleft()
ans.append([cur_node, cur_dist])
# visited[cur_node] = True
for next_node in temp[cur_node]:
if not visited[next_node]:
queue.append((next_node, cur_dist + 1))
visited[next_node] = True
return ans
chat gpt sensei code
from collections import defaultdict, deque
def solution(n, edge):
visited = [False for _ in range(n+1)]
temp = defaultdict(list)
for start, end in edge:
temp[start].append(end)
temp[end].append(start)
queue = deque()
queue.append((1, 0))
visited[1] = True
max_distance = 0
count = 0
while queue:
cur_node, cur_dist = queue.popleft()
if cur_dist > max_distance:
max_distance = cur_dist
count = 1
elif cur_dist == max_distance:
count += 1
for next_node in temp[cur_node]:
if not visited[next_node]:
queue.append((next_node, cur_dist + 1))
visited[next_node] = True
return count
무인도 여행
https://school.programmers.co.kr/learn/courses/30/lessons/154540
ok so 2 things when ur adding to queue, the last marked grid to X might be explored in the last element in the queue so i need to check if that is x or not and if not we add it to sum. secondly my next x and next y range limit was wrong. next_x is not mathematical x it is the row so len(graph)
Also, instead of just marking visited grid as X, a separate visited list will be more helpful because then i wont need as many checks
my initial wrong code:
def solution(maps):
rows = len(maps)
cols = len(maps[0])
graph = []
for row in maps:
graph.append(list(row))
print(graph)
# visited = [[False for _ in range(cols)] for _ in range(rows)]
moves = [[1,0],[0,1],[-1,0],[0,-1]]
answer = []
queue = deque()
for i in range(rows):
for j in range(cols):
if(graph[i][j]!='X'):
queue.append((i,j))
answer.append(bfs(graph,queue,moves))
print(answer.sort())
return answer.sort()
def bfs(graph,queue,moves):
sum=0
while queue:
cur_x,cur_y = queue.popleft()
cur_cost = graph[cur_x][cur_y]
sum+= int(cur_cost)
graph[cur_x][cur_y]='X'
for move in moves:
next_x=move[0]+cur_x
next_y=move[1]+cur_y
if next_x<0 or next_x>=len(graph[0]) or next_y<0 or next_y>=len(graph) or graph[next_x][next_y]=='X':
continue
queue.append((next_x,next_y))
return sum
solution(["X591X","X1X5X","X231X", "1XXX1"])
Then I still have an error like
from collections import deque
def solution(maps):
rows = len(maps)
cols = len(maps[0])
graph = []
for row in maps:
graph.append(list(row))
print(graph)
# visited = [[False for _ in range(cols)] for _ in range(rows)]
moves = [[1,0],[0,1],[-1,0],[0,-1]]
answer = []
queue = deque()
for i in range(rows):
for j in range(cols):
if(graph[i][j]!='X'):
queue.append((i,j))
answer.append(bfs(graph,queue,moves))
answer.sort()
# print(answer)
return answer if len(answer)>0 else [-1]
def bfs(graph,queue,moves):
sum=0
while queue:
cur_x,cur_y = queue.popleft()
cur_cost = graph[cur_x][cur_y]
if cur_cost!='X':
sum+= int(cur_cost)
graph[cur_x][cur_y]='X'
for move in moves:
next_x=move[0]+cur_x
next_y=move[1]+cur_y
if next_x<0 or next_x>=len(graph) or next_y<0 or next_y>=len(graph[0]) or graph[next_x][next_y]=='X':
continue
queue.append((next_x,next_y))
return sum
The error is that we should only go on with the dfs search if cur_cost!=’x’ so we need to indent properly. And also just use a separate visited list like
from collections import deque
def solution(maps):
rows = len(maps)
cols = len(maps[0])
graph = []
for row in maps:
graph.append(list(row))
print(graph)
# visited = [[False for _ in range(cols)] for _ in range(rows)]
moves = [[1,0],[0,1],[-1,0],[0,-1]]
answer = []
queue = deque()
for i in range(rows):
for j in range(cols):
if(graph[i][j]!='X'):
queue.append((i,j))
answer.append(bfs(graph,queue,moves))
answer.sort()
# print(answer)
return answer if len(answer)>0 else [-1]
def bfs(graph,queue,moves):
sum=0
while queue:
cur_x,cur_y = queue.popleft()
cur_cost = graph[cur_x][cur_y]
if cur_cost!='X':
sum+= int(cur_cost)
graph[cur_x][cur_y]='X'
for move in moves:
next_x=move[0]+cur_x
next_y=move[1]+cur_y
if next_x<0 or next_x>=len(graph) or next_y<0 or next_y>=len(graph[0]) or graph[next_x][next_y]=='X':
continue
queue.append((next_x,next_y))
return sum
리코체 로봇
https://school.programmers.co.kr/learn/courses/30/lessons/169199
Original my wrong code:
from collections import deque
def solution(board):
graph = []
for row in board:
graph.append(list(row))
row = len(graph)
col = len(graph[0])
for i in range(row):
for j in range(col):
if graph[i][j] == 'R':
val = bfs(graph, i, j)
return val
def bfs(graph, i, j):
queue = deque()
queue.append((i, j, 0))
moves = [[1, 0], [-1, 0], [0, 1], [0, -1]]
row = len(graph)
col = len(graph[0])
while queue:
cur_x, cur_y, cur_cost = queue.popleft()
if graph[cur_x][cur_y] == 'G':
return cur_cost
for move in moves:
next_x, next_y, next_cost = 0, 0, 0
for i in range(1, row):
if move[0]*i + cur_x < 0 or move[0]*i + cur_x >= row or move[1]*i + cur_y < 0 or move[1]*i + cur_y >= col:
next_x = move[0]*(i) + cur_x
next_y = move[1]*(i) + cur_y
next_cost = cur_cost + 1
queue.append((next_x, next_y, next_cost))
break
elif graph[move[0]*i + cur_x][move[1]*i + cur_y] == 'D':
next_x = move[0]*(i-1) + cur_x
next_y = move[1]*(i-1) + cur_y
next_cost = cur_cost + 1
queue.append((next_x, next_y, next_cost))
break
return -1
result = solution(["...D..R", ".D.G...", "....D.D", "D....D.", "..D...."])
print(result)
If I implement this way where I am adding 1 up to max row or column, the implementation is very complicated. An improvement would be to use a while loop to check as long as the next position of x and y when move is added doesnt go out of bounds, we keep updating next position of x and y.
V important. For this question I was wrongly adding invalid next_x and next_y to my queue that went beyond the boundary of the board.
Wrong:
for move in moves:
next_x, next_y = cur_x, cur_y
while 0<=next_x < row and 0<=next_y< col and graph[next_x][next_y] != 'D':
next_x+=move[0]
next_y+=move[1]
if distance[next_x][next_y]>cur_cost+1:
distance[next_x][next_y]=cur_cost+1
queue.append((next_x,next_y,cur_cost+1))
Correct:
for move in moves:
next_x, next_y = cur_x , cur_y
while 0<=next_x+move[0] < row and 0<=next_y+move[1]< col and graph[next_x+move[0]][next_y+move[1]] != 'D':
next_x+=move[0]
next_y+=move[1]
if distance[next_x][next_y]>cur_cost+1:
distance[next_x][next_y]=cur_cost+1
queue.append((next_x,next_y,cur_cost+1))
In my wrong code, there is actually no point checking that boundary condition cuz we are essentially checking current position and not the next position. WTF. We should be checking the next position like while 0<=cur_x+move[0]<row then we update next position via next_x +=move[0]
Gpt improvement:
for move in moves:
next_x, next_y = cur_x, cur_y
while True:
next_x += move[0]
next_y += move[1]
if not (0 <= next_x < row and 0 <= next_y < col) or graph[next_x][next_y] == 'D':
break
Ok that is good but you can use a visited set instead of distance 2d list. I had some doubts of using visited set here because
for visited set what if we have visited a position before but greater distance is taken but the this visit has a shorter distance but since it is a set we cant explore this path. or does this possibility not occur?
Gpt sensei explained it well:
this is not an issue because of the nature of the problem and the way the BFS is implemented. Since the robot can only move in four directions (up, down, left, right) and the board contains walls (‘D’) that block the path, the shortest path from the robot to the goal can always be found correctly by using BFS without the need to revisit a position with a different distance. The reason is that BFS always explores all possible paths layer by layer. When a position is first visited, it is guaranteed that the shortest distance to reach that position has been found. Any subsequent visits to the same position with longer distances will be discovered in later iterations, and they won’t affect the correctness of the result because BFS guarantees that it explores all possible paths systematically. In other words, the shortest path from the robot to the goal will always be found and explored first, and any other longer paths to the same position won’t affect the final result. Therefore, using a set for the visited container is sufficient and efficient for this specific problem
BFS search is layer by layer so if that positon is visited, it is a guarantee that a shortest distance has been used to visit that position. Other future visits to that same positon will be longer distance because BFS is layer by layer.
def solution(board):
que = []
for x, row in enumerate(board):
for y, each in enumerate(row):
if board[x][y] == 'R':
que.append((x, y, 0))
visited = set()
while que:
x, y, length = que.pop(0)
if (x, y) in visited:
continue
if board[x][y] == 'G':
return length
visited.add((x, y))
for diff_x, diff_y in ((0, 1), (0, -1), (1, 0), (-1, 0)):
now_x, now_y = x, y
while True:
next_x, next_y = now_x + diff_x, now_y + diff_y
if 0 <= next_x < len(board) and 0 <= next_y < len(board[0]) and board[next_x][next_y] != 'D':
now_x, now_y = next_x, next_y
continue
que.append((now_x, now_y, length + 1))
break
return -1