Python Algorithms - DFS/BFS - "Freeze beverages"

Sunmi Shin·2022년 11월 12일

Python Algorithms

목록 보기
5/7
post-thumbnail

Problem:
How many frozen beverages(icecream) can you produce when given following ice frames?
얼음 틀이 주어졌을 때 얼마나 많은 아이스크림을 구할 수 있는가?

Example:
4 X 5 ice frame makes 3 icecreams in total.

00110
00011
11111
00000

#Get input N and M. 
n, m = map(int, input().split())

#Get a sequential numbers of input and 
#put it into 2 dimensional list, "graph". 
graph = []
for _ in range(n):
	graph.append(list(map(int, input())))

#Define a function named "dfs".
def dfs(x, y):
	#Return False if x and y are out of range N X M. 
	if x <= -1 or x >= n or y <= -1 or y >= m:
    	return False
    
    #If the node (x, y) is not "visited", code it to 1.
    if graph[x][y] ==0:
    	graph[x][y] = 1
        
        #Call the "dfs" function recursively and check the surrounding nodes 
        #whether they are visited.
        dfs(x-1, y)
        dfs(x, y-1)
        dfs(x+1, y)
        dfs(x, y+1)
        
        #Return True if they are visited. 
        return True
    return False
    
result = 0
#In a for-loop of N X M, if the node(i, j) was visited, count 1 up for result. 
for i in rangae(n):
	for j in range(m):
    	if dfs(i, j) == True:
    		result += 1
print(result)
profile
Tempest Data Analyst

0개의 댓글