[백준] 2667번 단지번호붙이기

https://www.acmicpc.net/problem/2667

Initial

My approach was to conduct DFS when we come across a grid that is value 1.

from collections import defaultdict, deque


n = int(input())
graph = [list(map(int, input().strip())) for _ in range(n)]

moves = [[1,0],[0,1],[-1,0],[0,-1]]


def dfs(graph,i,j):
    global count
    graph[i][j]=0
    count +=1
    if i<0 or i>=len(graph) or j<0 or j>=len(graph[0]):
        return
    for move in moves:
        next_x = move[0]+i
        next_y = move[1]+j
        if graph[next_x][next_y]==1:
            dfs(graph,next_x,next_y)


result = 0
count = 0
ans=[]
for i in range(len(graph)):
    for j in range(len(graph[0])):
        if graph[i][j]==1:
            dfs(graph,i,j)
            ans.append(count)
            result +=1
            count =0

print(result)

However, look at this code

    for move in moves:
        next_x = move[0]+i
        next_y = move[1]+j
        if graph[next_x][next_y]==1:
            dfs(graph,next_x,next_y)

My wrong code did not check for the boundarys for the next x and y. Thus, when we go to that dfs(next_x,next_y) and do graph[next_x][next_y], we get list index out of range.

Solution

I haven't seen this way of implementation where you set DFS return type as boolean. And to prevent list index out of range for graph[next_x][next_y] when next_x and next_y are values bigger than the boundaries of the board, we can first just pass those paramters to our dfs function like dfs(next_x,next_y). Then, in the deeper recursive call, we set the boundary constraint limit. So if current position is out of boundaries or not 1, we return False immediately.

Also, the bane of DFS in python is updating the count variable. We use global to update global count and increment that value when we have valid conditions. When we finish with the DFS search, we MUST reset count to 0 for the future DFS iterations.

from collections import defaultdict, deque


n = int(input())
graph = [list(map(int, input().strip())) for _ in range(n)]

moves = [[1,0],[0,1],[-1,0],[0,-1]]


def dfs(graph,i,j):
    global count
    if i<0 or i>=len(graph) or j<0 or j>=len(graph[0]):
        return False
    if graph[i][j]==1:
        # global count
        graph[i][j]=0
        count +=1
        for move in moves:
            next_x = move[0]+i
            next_y = move[1]+j
            dfs(graph,next_x,next_y)
        return True
    return False


result = 0
count = 0
ans=[]
for i in range(len(graph)):
    for j in range(len(graph[0])):
        if dfs(graph,i,j):
            ans.append(count)
            result +=1
            count =0
ans.sort()

print(result)
for num in ans:
    print(num)

[revisited jan 9th 24] ok good. also resetting count to 0 is a nice trick. Since 1 dfs will update count variable to grid area, after dfs has ended we reset count to 0 for next dfs search to start with grid area of 0.

revisited may 15th

we dont need to make dfs boolean. BTW i struggled cuz there is no specific end condition for this dfs search so how do i return the final count? I cant return since there is no end condition.

For this, we use a global count variable and increment that value as we dfs search. When we finish and there are no more valid options, we append that count variable to a list. VERY impt, for next dfs, we need to reset that global count variable to 0.

n=int(input())
graph=[]
for _ in range(n):
    split = input().strip()
    graph.append(list(map(int,split)))

moves=[[1,0],[-1,0],[0,1],[0,-1]]
ans=[]
count=0
def dfs(x,y):
    global count
    count+=1
    for move in moves:
        next_x, next_y = move[0]+x, move[1]+y
        if 0<=next_x<n and 0<=next_y<n:
            if graph[next_x][next_y]==1:
                graph[next_x][next_y]=0
                dfs(next_x,next_y)

for i in range(n):
    for j in range(n):
        if graph[i][j]==1:
            graph[i][j]=0
            dfs(i,j)
            ans.append(count)
            count =0

ans.sort()
print(len(ans))
for i in ans:
    print(i)

complexity

Time Complexity:

1. DFS Traversal: The core of the code is the Depth-First Search (DFS) traversal through the binary grid represented by the graph variable. The code uses a recursive DFS approach to explore connected components.

   • In the worst case, the DFS traversal can visit every cell in the grid once.
   • The DFS traversal runs in O(V + E) time, where V is the number of vertices (cells) and E is the number of edges (connections between adjacent cells).
   • In this case, V is equal to the total number of cells in the grid (n x n), and E depends on the structure of the grid but is typically less than V.
   • Therefore, the DFS traversal can be considered to run in O(n^2) time in the worst case.

2. Sorting ans List: After completing the DFS traversal for all connected components, the code sorts the ans list, which contains the sizes of connected components.

   • Sorting a list of size n typically takes O(n log n) time complexity.

Overall, the dominant time complexity is the DFS traversal, so the overall time complexity of the code is O(n^2) in the worst case due to the DFS traversal.

Space Complexity:

1. Input Data: The graph variable stores the binary grid, which requires O(n^2) space as it has n rows and n columns.

2. Recursion Stack: During the DFS traversal, the code uses the call stack to keep track of recursive function calls. The maximum depth of the recursion is limited to the size of the grid, which is O(n^2) in the worst case. Therefore, the space complexity due to the recursion stack is O(n^2).

3. Other Variables: The code uses some additional variables (e.g., moves, count, result, and ans) that consume a constant amount of space, so they don't significantly impact the overall space complexity.

Overall, the dominant space complexity components are the input data (graph) and the recursion stack, both of which are O(n^2) in the worst case.

In summary, the time complexity is O(n^2), and the space complexity is O(n^2) in the worst case for the provided code when analyzing its worst-case behavior in terms of grid size.