[BOJ] 1012. 유기농 배추

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

1012번: 유기농 배추

 

 

1. 해결방법

"""
1. 아이디어
- BFS를 돌면서 배추가 심어진, 즉 그래프 상에서 1로 연결된 지점을 돌면서 끝나면 +1을 해준다.
- 방문기록을 체크하면서 이중 for문을 돈다.

2. 시간복잡도
- O(V + E)

3. 자료구조
- BFS
- 2중 for문
"""

 

 

2. 정답코드

입력 예제(1)

2
10 8 17
0 0
1 0
1 1
4 2
4 3
4 5
2 4
3 4
7 4
8 4
9 4
7 5
8 5
9 5
7 6
8 6
9 6
10 10 1
5 5

출력 예제(1)

5
1

 

입력 예제(2)

1
5 3 6
0 2
1 2
2 2
3 2
4 2
4 0

출력 예제(2)

2

 

 

코드

from collections import deque
import sys
input = sys.stdin.readline


t = int(input())


dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

# bfs
def bfs(y, x, graph, chk):
    q = deque()
    q.append((y, x))
    chk[y][x] = True

    while q:
        ey, ex = q.popleft()
        for i in range(4):
            ny = ey + dy[i]
            nx = ex + dx[i]
            if 0 <= ny < n and 0 <= nx < m:
                if chk[ny][nx] == False and graph[ny][nx] == 1:
                    q.append((ny, nx))
                    chk[ny][nx] = True


# main
for _ in range(t):
    m, n, k = map(int, input().split())
    graph = [[0] * m for _ in range(n)]
    chk = [[False] * m for _ in range(n)]
    count = 0

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

    for a in range(n):
        for b in range(m):
            if graph[a][b] == 1 and chk[a][b] == False:
                bfs(a, b, graph, chk)
                count += 1

    print(count)