1seul357

[BOJ] 유기농 배추 본문

알고리즘/백준

[BOJ] 유기농 배추

1seul 2021. 12. 7. 10:19
def bfs(row, col):
    dr = [-1, 1, 0, 0]
    dc = [0, 0, -1, 1]
    q.append([row, col])
    while len(q) != 0:
        x, y = q.pop(0)
        for i in range(4):
            now_dr = x + dr[i]
            now_dc = y + dc[i]
            if 0 <= now_dr < N and 0 <= now_dc < M:
                if visited[now_dr][now_dc] == 0 and MAP[now_dr][now_dc] == 1:
                    visited[now_dr][now_dc] = 1
                    q.append([now_dr, now_dc])

T = int(input())
for TC in range(T):
    N, M, K = map(int, input().split())
    MAP = [[0]*M for _ in range(N)]
    visited = [[0]*M for _ in range(N)]
    cnt = 0
    q = []
    ans = []

    for i in range(K):
        x, y = map(int, input().split())
        MAP[x][y] = 1

    for i in range(N):
        for j in range(M):
            if MAP[i][j] == 1 and visited[i][j] == 0:
                cnt += 1
                visited[i][j] = 1
                bfs(i, j)

    print(cnt)

'알고리즘 > 백준' 카테고리의 다른 글

[BOJ] 양  (0) 2021.12.09
[BOJ] 숨바꼭질  (0) 2021.12.07
[BOJ] 블랙잭  (0) 2021.12.07
[BOJ] 바이러스  (0) 2021.12.07
[BOJ] 탑  (0) 2021.12.04