[백준] 1012번 유기농 배추 파이썬 정답 코드

1012번: 유기농 배추

---

1. 문제 내용

 

 

2. 접근 방식

• 배추가 심어져 있는 땅을 입력받는다.

maps 2차원 리스트를 모두 0으로 초기화한 다음에, 배추가 심어져 있는 장소를 1로 바꾸면 된다. 또한 배추가 심어져 있는 땅, 즉 1인 칸의 위치를 알고 있기 때문에 아직 방문하지 않은 배추가 심어진 땅을 대상으로만 bfs( ) 메서드를 실행하면 된다.

 

 

3. 정답 코드

from collections import deque


def make_maps(ks):
    graph = [[0] * n for _ in range(m)]

    for v in ks:
        graph[v[0]][v[1]] = 1

    return graph


def bfs(i, j):
    visited[i][j] = True

    queue = deque([[i, j]])
    while queue:
        x, y = queue.popleft()

        for d in directions:
            dx = x + d[0]
            dy = y + d[1]

            if dx >= m or dx < 0 or dy >= n or dy < 0:
                continue

            if not visited[dx][dy] and maps[dx][dy]:
                visited[dx][dy] = True
                queue.append([dx, dy])

    return 1


t = int(input())
for test_case in range(1, t + 1):
    m, n, k = map(int, input().split())
    data = [list(map(int, input().split())) for _ in range(k)]

    maps = make_maps(data)
    visited = [[False] * n for _ in range(m)]
    directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]

    results = 0
    for pair in data:
        if not visited[pair[0]][pair[1]]:
            results += bfs(pair[0], pair[1])

    print(results)