[BOJ] #1012 유기농 배추

유기농 배추

백준 #1012

---

📌 문제

예제 입력

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

---

📌 풀이

Logic

• 테스트 케이스 개수 T 입력 받기
• N * M 배추밭 크기 & 배추 개수 K 입력 받기
• board, visited 리스트 생성 <- 백트래킹(BackTracking)
• BFS 함수 구현(deque)
  • 현재 위치에서 4방향 이동 가능 여부 확인
  • 이동 가능 시 deque 추가, deque 비었으면 해당 영역 종료
• 배추밭 전체 bfs(p, q)로 탐색 & cnt로 영역 개수 출력

# 변수명
case : 테스트 케이스 수
N, M : 배추밭 크기
K : 배추 개수
board : 배추밭 리스트
visited : 백트래킹을 위한 리스트

dq : 현재 위치에서 이동가능한 위치의 좌표들을 담아두는 deque
cnt : 영역의 수

Python

import sys
from collections import deque

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

def bfs(x, y):
    dq = deque()
    dq.append((x, y))
    visited[x][y] = 1

    while dq:
        cur_x, cur_y = dq.popleft()

        for i in range(4):
            nx = cur_x + dx[i]
            ny = cur_y + dy[i]

            if ((0 <= nx < N) and (0 <= ny < M)):
                if (board[nx][ny] == 1 and visited[nx][ny] == 0):
                    visited[nx][ny] = 1
                    dq.append((nx, ny))

case = int(sys.stdin.readline())

for _ in range(case):
    M, N, K = map(int, sys.stdin.readline().split())

    board = [[0] * M for _ in range(N)]
    visited = [[0] * M for _ in range(N)]

    for _ in range(K):
        coord_x, coord_y = map(int, sys.stdin.readline().split())

        board[coord_y][coord_x] = 1

    cnt = 0

    for p in range(N):
        for q in range(M):
            if (board[p][q] == 1 and visited[p][q] == 0):
                bfs(p, q)
                cnt += 1

    print(cnt)

---

✏️ 새로운 내용

-

---

📚 회고

💡 영역의 수

• 단순히 bfs를 반복하는 것으로 끝이 아니다. 하나의 좌표에서 확산 가능한 영역들은 묶어서 1개로 세야한다.
• bfs 함수 내에서 if문으로 4방향 탐색 가능 여부를 확인하지만, 기본적으로 한 점에서 시작되는 영역은 cnt로 저장해야 한다. 따라서 같은 형태의 if문이 bfs 함수를 호출할 때도 적용된다.