[백준] 1012번: 유기농 배추

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

INITIAL

a very typical BFS question that is easy. but i made careless mistake of making it 1-indexed but it should have been 0-indexed.

I made bfs make nearby grids all 0

solution

from collections import deque

def bfs(i, j):
    moves = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    queue = deque()
    queue.append((i, j))
    visited[i][j] = True

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

t = int(input())
for _ in range(t):
    n, m, k = map(int, input().split())
    graph = [[0 for _ in range(m)] for _ in range(n)]
    visited = [[False for _ in range(m)] for _ in range(n)]

    for _ in range(k):
        a, b = map(int, input().split())
        graph[a][b] = 1

    ans = 0

    for i in range(n):
        for j in range(m):
            if graph[i][j] and not visited[i][j]:
                bfs(i, j)
                ans += 1

    print(ans)

complexity

The time complexity of your code is primarily determined by the breadth-first search (BFS) algorithm used to traverse the graph. Here's the analysis of the time complexity:

1. Graph Initialization: Creating the graph and visited matrices takes O(n * m) time, where 'n' is the number of rows, and 'm' is the number of columns.

2. BFS Traversal: The BFS algorithm explores each connected component of the graph exactly once. The worst-case time complexity for BFS is O(V + E), where V is the number of vertices (nodes) and E is the number of edges in the connected component.

   In your code, you iterate over all cells in the graph. If a cell is part of a connected component, the BFS will traverse that entire component. So, in the worst case, your BFS complexity for one connected component is O(n * m) since it can visit every cell in the grid.

3. Outer Loop: Your code has an outer loop that runs 't' times, which corresponds to the number of test cases. Therefore, the overall time complexity is O(t n m) in the worst case.

Overall, your code's time complexity is O(t n m) because it processes 't' test cases, and for each test case, it processes an n x m grid with BFS.

Please note that if you have additional operations or calculations within the BFS or other parts of your code, the overall time complexity may change.