Python - [백준 1012] 유기농 배추 (feat. BFS, 연결요소)

 

참고 포스트:

2024.12.22 - [Computer Science/알고리즘 문제] - C - [백준 11724] 연결 요소의 개수 (feat. 배열)

C - [백준 11724] 연결 요소의 개수 (feat. 배열)

 

 

---

Checkpoint

 

BFS 와 연결요소에 관한 지식이 있으면 쉽게 풀 수 있습니다.

예전에 풀었던  BOJ_11724)_연결요소의 개수( https://rnasterofmysea.tistory.com/48 ) 와 동일한 문제네요.

 

1️⃣ 배추밭을 2차원 리스트로 표현

• M x N 크기의 2차원 리스트(farm)를 생성하여 배추가 있는 곳을 1로 설정.
• visited 리스트를 사용하여 방문 여부를 체크.

2️⃣ 모든 배추 위치에서 BFS 탐색

• 배추가 있는 위치 중 아직 방문하지 않은 곳을 찾으면 새로운 배추 군집을 발견한 것이므로 count 증가.
• BFS를 사용하여 인접한 배추들을 모두 방문 처리.

3️⃣ BFS를 활용한 최단 거리 탐색

• 큐(deque)를 사용하여 탐색을 수행.
• 현재 위치에서 상하좌우 이동하며 배추가 있고, 방문하지 않은 곳이면 큐에 추가.

---

📌 코드 구현

from collections import deque

# 방향 벡터 (상, 하, 좌, 우)
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

def bfs(y, x, farm, visited, M, N):
    queue = deque([(y, x)])
    visited[y][x] = 1  # 방문 처리

    while queue:
        cy, cx = queue.popleft()

        for i in range(4):  # 네 방향 탐색
            ny = cy + dy[i]
            nx = cx + dx[i]

            if 0 <= nx < M and 0 <= ny < N and farm[ny][nx] == 1 and visited[ny][nx] == 0:
                queue.append((ny, nx))
                visited[ny][nx] = 1  # 방문 처리

def count_worms(M, N, K, positions):
    # 배추밭 초기화
    farm = [[0] * M for _ in range(N)]
    visited = [[0] * M for _ in range(N)]

    # 배추 위치 설정
    for x, y in positions:
        farm[y][x] = 1  # (x, y) 좌표 주어지므로 y, x 순서로 배치

    count = 0
    for y in range(N):
        for x in range(M):
            if farm[y][x] == 1 and visited[y][x] == 0:
                bfs(y, x, farm, visited, M, N)
                count += 1  # 배추 군집 하나 추가

    return count

# 입력
T = int(input())  # 테스트 케이스 개수
for _ in range(T):
    M, N, K = map(int, input().split())  # 가로, 세로, 배추 개수
    positions = [tuple(map(int, input().split())) for _ in range(K)]  # 배추 위치
    print(count_worms(M, N, K, positions))

---

📌 코드 설명

1. 입력 처리
   • M, N, K를 입력받고 **배추 위치 리스트(positions)**를 생성.
   • farm[y][x] = 1로 배추 위치 표시.
   • visited[y][x] = 0으로 초기화.
2. BFS(너비 우선 탐색)로 배추 군집 탐색
   • 새로운 배추 군집을 찾을 때마다 bfs(y, x) 실행.
   • 방문한 모든 배추는 visited = 1로 처리.
3. 최종 배추 군집 개수 출력
   • count 변수에 배추 군집 개수를 저장하여 출력.

---

📌 예제 테스트

입력

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

출력

5
1

---

📌 결론

• ✅ BFS를 활용하여 인접한 배추들을 빠르게 탐색.
• ✅ 배추 군집을 효율적으로 찾기 위해 방문 여부(visited)를 활용.
• ✅ 최단 경로 탐색 방식(BFS) 적용으로 O(NM + K) 시간 복잡도를 유지.

 

 

---

 

💡 도움이 되셨다면 댓글과 공감 부탁드립니다! 😊
📌 더 많은 알고리즘 풀이와 프로그래밍 자료는 블로그에서 확인하세요!
✉️ 문의나 피드백은 댓글이나 이메일로 남겨주세요.