[백준] 2638번: 치즈

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

initial

it is very similar to that cheese question
https://velog.io/@whitehousechef/%EB%B0%B1%EC%A4%80-2636%EB%B2%88-%EC%B9%98%EC%A6%88

except now we only melt the cheese grids that have at least 2 neighbouring air grids.

Learning from that link, first we can traverse the outer edges of the graph by appending the air girds with value 0 to our queue. (revisit that link for deeper explanation).

Then, I thought how to implement this "at least 2 neighbouring air grids". I made a separate 2d count matrix of 0s and if we meet a cheese grid, we increment 1 each time we visit that grid. So we dont mark that grid as visited so that multiple visits can be done but the air grids HAVE to be marked as visited bcos our bfs queue will go into infinite loop.

After bfs search, we traverse through this 2d count list and if value is >=2, we melt away the cheese by marking the grid as 0. Then we do that bfs search again with 1 more time second.

solution

from collections import deque

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

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

def bfs():
    queue = deque()
    visited = [[False for _ in range(m)] for _ in range(n)]
    count = [[0 for _ in range(m)] for _ in range(n)]
    visited[0][0] = True
    queue.append((0, 0))
    flag = False

    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:
                if graph[next_x][next_y] == 0 and not visited[next_x][next_y]:
                    queue.append((next_x, next_y))
                    visited[next_x][next_y] = True
                elif graph[next_x][next_y] == 1:
                    count[next_x][next_y] += 1

    for i in range(n):
        for j in range(m):
            if count[i][j] >= 2:
                flag = True
                graph[i][j] = 0

    return flag

time = 0

while True:
    time += 1
    res = bfs()
    if not res:
        break

print(time-1)

COMPLEXITY

Your code appears to be an implementation of a breadth-first search (BFS) algorithm to traverse a grid and update cell values based on specific conditions. The BFS is performed to find connected regions of cells with value 1. Here's an explanation of your code and its time complexity:

1. You initialize the grid graph, and a list of possible moves in the moves variable.

2. The bfs function is used to perform the BFS traversal. It initializes a queue, a visited array to keep track of visited cells, and a count array to count the number of adjacent 1s in each cell.

3. Within the BFS loop, you visit cells one by one, and for each cell, you check its neighbors (up, down, left, right) to determine if they are valid and whether they are 0 or 1. If a neighboring cell is 0, it's marked as visited and added to the queue. If a neighboring cell is 1, the count for that cell is incremented.

4. After completing the BFS traversal, you iterate through the entire grid to check if any cells have a count greater than or equal to 2. If they do, it means there are at least two adjacent 1 cells, and you set the cell value to 0.

5. The bfs function returns a flag that indicates whether any changes were made during the BFS traversal.

6. In the main part of your code, you continuously call the bfs function and increment the time variable. The loop continues until the BFS traversal doesn't find any changes in the grid. This loop effectively finds and removes connected regions of 1 cells from the grid.

The time complexity of this code is primarily determined by the BFS traversal and the loop that keeps calling the BFS function until no changes are made. In the worst case, the BFS may traverse the entire grid for each connected region of 1s, resulting in a time complexity of O(n m (n + m)).

The space complexity is determined by the space used for the visited and count arrays, which are both O(n m) in size, as well as the space for the queue, which can also be up to O(n m) in the worst case. Therefore, the overall space complexity is O(n * m).

The code efficiently finds and removes connected regions of 1 cells from the grid using BFS.