알고리즘 스터디 - 백준 1012번 : 유기농 배추

문제 해석

• 한나가 강원도 고랭지에서 유기농 배추를 재배함
• 배추흰지렁이가 살고 있는 한 배추의 상하좌우 다른 배추들도 보호 받는다.
• 배추들이 모여있는 곳에는 배추 흰지렁이가 한 마리만 있으면 서로 인접해있는 배추들이 몇군데에 퍼져 있는지 조사하면 된다.

어떤 알고리즘을 사용해야할까?

1. 테스트 케이스의 개수 T
2. 배추밭의 가로길이 M, 세로길이 N, 위치의 개수 K
3. K개의 좌표 수

목표 : 각 테스트 케이스에 대해 필요한 최소의 배추흰지렁이 마리 수를 출력한다.

상하좌우로 움직이는 BFS 알고리즘을 사용하자

알고리즘 코드

T = int(input())

def bfs(x, y):
    # 상하좌우에 필요한 좌표
    dx = [0, 0, 1, -1]
    dy = [-1, 1, 0, 0]

    # 큐 선언
    q = []

    # 초기 좌표 삽입
    q.append((x, y))

    # 초기 좌표 방문한 것으로 바꾸고 넓이 더함
    area[y][x] = 0

    while q:
        x_, y_ = q.pop(0)

        for i in range(4):
            new_x_ = x_ + dx[i]
            new_y_ = y_ + dy[i]
            if 0 <= new_x_ < M and 0 <= new_y_ < N and area[new_y_][new_x_] == 1:
                area[new_y_][new_x_] = 0
                q.append((new_x_, new_y_))
    
    return 1

for _ in range(T):
    M, N, K = map(int, input().split())

    area = [[0] * M for _ in range(N)]
    
    for _ in range(K):
        m, n = map(int, input().split())
        area[n][m] = 1
    
    larva = 0
    for i in range(N):
        for j in range(M):
            if area[i][j] == 1:
                larva += bfs(j, i)

    print(larva)