[백준] 2636번: 치즈

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

initial

This is a hard BFS question and I have never handled such a question that traverses just the outer edges of our graph.

i initially thought of dfs like making depth 0 grids as 0 and depth 1 grids as 1 and so on but that doesn't work. Then I thought BFS but wasnt sure how to implement this.

To make it harder, we don't traverse the inner hole of our graph even if there is a bunch of 0s within our graph of 1s. 2) And calculate time to make it all 0s
3) AND calculate how many cheese grids there are just before our graph all turns to 0

So this question requires not just bfs but general implementation skills

solution

1) first for bfs, The way to do this is to append the non-cheese grids to our queue. for example

6 6
0 0 0 0 0 0
0 1 1 1 1 0
0 1 1 0 1 0
0 1 0 0 1 0
0 1 1 1 1 0
0 0 0 0 0 0

we have added starting point 0,0 to our queue and we will only have choice to go from there. If we don't, then the inner area consiting of those 3 0s will be wrongly added to our queue and melt the cheese from inside out. That is wrong because we only want to melt the cheese from the outer surroundings.

we will initialise a new and fresh visited list for each time passing. We append position that is value 0 to our queue and if it is cheese grid of value 1, then we just make it 0 and not append to queue. For both types of grids, we mark grid as visited so that future traversals don't add this to our queue since it will be value 0.

2) when all cheese grids become 0, then we return time. That is when even after our bfs loop finishes, count will still be 0 bcos no 1s will be left. so return time-1 then.

3) we append number of 1s for each bfs loop to our ans list [] and append ans[-2] (not -1 bcos for index -1, it will be 0 since all cheese grids will be turned to 0 and our count will be 0).

import sys
from collections import deque

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


ans=[]

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

def bfs():
    queue =deque()
    visited[0][0]=True
    queue.append((0,0))
    count=0
    while queue:
        cur_x,cur_y= queue.popleft()
        for move in moves:
            next_x,next_y = move[0]+cur_x, move[1]+cur_y
            if 0<=next_x<n and 0<=next_y<m and not visited[next_x][next_y]:

                if graph[next_x][next_y]==0:
                    queue.append((next_x,next_y))
                    visited[next_x][next_y]=True
                elif graph[next_x][next_y]==1:
                    graph[next_x][next_y]=0
                    visited[next_x][next_y]=True
                    count+=1
    ans.append(count)
    return count
time=0
while True:
    time+=1
    visited = [[False for _ in range(m)] for _ in range(n)]
    count = bfs()
    if count==0:
        break
print(time-1)
print(ans[-2])

complexity

The given code appears to perform a Breadth-First Search (BFS) on a 2D grid to determine the time it takes to remove all connected regions of '1's from the grid. Here's the complexity analysis of the code:

1. Reading Input: Reading the input grid has a time complexity of O(n * m), where n is the number of rows and m is the number of columns in the grid.

2. BFS Function (bfs): The BFS function performs a BFS traversal on the grid. In the worst case, it can visit each cell of the grid once. Therefore, the time complexity of the BFS function is O(n * m).

3. Main Loop (while True): The main loop keeps executing the BFS until there are no more '1' regions in the grid. In the worst case, this loop may run for a maximum of n m times (one BFS for each cell). So, the time complexity of this loop is O(n m).

4. Visited Array Initialization: Creating and initializing the visited array inside the main loop has a time complexity of O(n * m).

5. BFS Calls: The number of times the BFS function is called depends on the number of connected regions of '1's in the grid. In the worst case, there could be n m connected regions. Therefore, the number of BFS calls is O(n m).

6. Appending to 'ans' List: Appending the count to the 'ans' list is done once for each connected region, and the size of the 'ans' list is equal to the number of connected regions. So, this has a time complexity of O(n * m).

In summary, the overall time complexity of the code is dominated by the BFS operations and is roughly O(n m) in the worst case, where n is the number of rows and m is the number of columns in the grid. The code performs BFS on each connected region of '1's, and the number of regions can affect the actual time taken to complete the algorithm. space is nm too.