[백준/python] 1012번: 유기농 배추

문제

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

1012번: 유기농 배추

---

문제 요약

N × M 크기의 배추 밭에서 배추가 심어져 있는 위치들을 입력 받고 배추흰지렁이가 최소 몇 개 필요한지 출력한다.

 

+ 배추흰지렁이는 상, 하, 좌, 우 네 방향의 인접한 배추가 있다면 이동할 수 있다.

---

코드

import sys
input = __import__('sys').stdin.readline
from collections import deque # 추


def flood_fill():
    check[i][j] = val # 방문한 곳 색칠
    q.append((i, j)) # 큐에 방문한 인덱스 추가
    while q:
    # 큐에 더이상 요소가 없을 때까지
        x, y = q.popleft() # 튜플 언패킹!!
        for k in range(4):
            nx, ny = x + dx[k], y + dy[k]
            if 0 <= nx < N and 0 <= ny < M and arr[nx][ny] and not check[nx][ny]:
            # (i, j)에서 파생된 4방향의 인덱스들이 배열의 범위에 속하는지
            # 배추가 있는 곳인데
            # 아직 색칠하지 않은 곳인지
                check[nx][ny] = val # 색칠
                q.append((nx, ny)) # 방문한 인덱스 큐애 추가        

T = int(input())

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

for _ in range(T):
    M, N, K = map(int, input().rstrip().split())
    # M은 가로 길이, N은 세로길이, K는 배추가 심어진 위치 개수
    arr = [[0] * M for _ in range(N)] # 배추 밭

    for _ in range(K):
        y, x = map(int, input().rstrip().split())
        arr[x][y] = 1 # 배추가 심어진 곳을 1로 설정

    check = [[0] * M for _ in range(N)] # 방문한 인덱스를 색칠할 배추밭
    val = 1 # check에 부여할 숫자. (색칠)

    q = deque() # 큐 생성

    for i in range(N):
        for j in range(M):
            if check[i][j] == 0 and arr[i][j] == 1:
            # 해당 인덱스가 배추가 있는 곳인데 아직 방문하지 않은 곳이면
                flood_fill() # 인접한 구역에 더 색칠할 구역이 있는지 찾는 함수
                val += 1 # 연결된 구역 색칠이 끝났으므로 다른 색으로 색칠

    print(val - 1) # val을 0부터 시작할 수는 없으므로 (칠하지 않은 구역이 0)

---

코드 설명

1. 배추 밭 크기의 2차원 배열 arr을 생성하고, 입력 받은 배추가 심어진 인덱스를 1로 설정한다.

 

2. 배추 밭 크기의 2차원 배열 check와 check에 부여할 숫자 val(초기 값 1)을 생성한다.

+ check는 방문한 인덱스를 색칠할 또 다른 배열, val은 check를 색칠할 색이다.

 

3. 이중 반복문을 이용해서 배추 밭의 모든 인덱스를 차례대로 검사한다.

 

3-1. 해당 인덱스가 배추가 있는 곳인데 아직 방문하지 않은 곳. 즉 색칠해야 하는 인덱스라면 flood_fill 함수를 호출한다.

+ flood_fill 함수는 인접한 인덱스에 더 색칠할 곳이 있는 지 찾고 val색으로 check 배열을 칠한다.

 

3-2. flood_fill 함수를 통해 모든 인접한 곳을 val로 색칠했다면, val에 1을 더해 다음 색칠할 구역은 다른 색으로 색칠한다.

 

4. flood_ fill 함수는 먼저 호출한 시점의 인덱스를 색칠하고 큐에 인덱스를 추가한다.

 

4-1. 큐에서 인덱스 x, y를 빼서 네 방향의 인접한 인덱스 (x - 1, 0), (x + 1, 0), (x, y - 1), (x, y + 1) 들을 탐색한다.

 

4-2. 인접한 인덱스 중 배추밭 배열 범위를 벗어나지 않으면서, 배추가 있는 곳이지만 아직 색칠되지 않은 곳이 있다면 색칠하고 큐에 그 인덱스를 넣는다.

 

4-3. 다시 큐에서 인덱스를 빼고 위 과정을 큐에 더이상 요소가 없을 때까지 반복한다.

 

5. val은 1부터 시작했으므로, val - 1 값이 칠한 구역의 개수이다.

---

이 문제는 그래프에서 연결 요소의 개수를 구하는 플러드 필 알고리즘 문제이다.

 

BFS (넓이 우선 탐색)으로 큐를 이용하여 구현할 수 도 있고,

 

DFS (깊이 우선 탐색)으로 재귀 함수를 이용해서도 구현할 수 있다.

 

import sys
input = __import__('sys').stdin.readline

sys.setrecursionlimit(10000)

def flood_fill(x, y):
    for d in range(4):
        nx, ny = x + dx[d], y + dy[d]
        if 0 <= nx < N and 0 <= ny < M and arr[nx][ny] and not check[nx][ny]:
            check[nx][ny] = val
            flood_fill(nx, ny)

T = int(input())

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

for _ in range(T):
    M, N, K = map(int, input().rstrip().split())
    arr = [[0] * M for _ in range(N)]
    check = [[0] * M for _ in range(N)]
    max_cnt = 0
    val = 1

    for _ in range(K):
        y, x = map(int, input().rstrip().split())
        arr[x][y] = 1

    for i in range(N):
        for j in range(M):
            if arr[i][j] and not check[i][j]:
                check[i][j] = val
                flood_fill(i, j)
                val += 1

    print(val - 1)

 

위 코드는 BFS를 이용해 구현한 코드이다.