플러드 필

Last updated 3 years ago

시뮬레이션

플러드 필 알고리즘은 BFS와 DFS를 이용한 테크닉이라고 생각하시면 편합니다. 그렇다고 BFS, DFS에 대해 자세하게 배워야 할 내용은 아니고, 그래프 알고리즘 소개 파트에서 배운 대로 BFS는 큐에 좌표를 넣고, DFS는 재귀 함수를 이용하여 풀 수 있습니다.

플러드 필

플러드 필 알고리즘은 그래프에서 연결 요소의 개수를 구하는 테크닉입니다. 연결 요소란 말 그대로 서로 간선이 연결된 정점이 몇 개인지 구하는 알고리즘입니다. 글을 읽고 문제를 풀어보면 알겠지만, 색칠하는 알고리즘이라고 생각하면 이해하기 쉽습니다.

삼성 기출 문제들은 전부 2차원 배열로 이루어진 문제로 이루어져 있기 때문에 우리는 2차원 배열로 이루어진 문제만 풀 것입니다.

우리가 처음 풀 문제인데, 여기에 나온 예제 1 값을 2차원 배열로 그려보면 다음과 같습니다. 문제 본문에도 나옵니다.

참고로 그림에서는 노드만 나와 있지만, 상하좌우로 연결된 간선이 있다고 생각하면 편합니다. 좀 더 쉽게 예시를 들자면 한 공간(노드)에 상하좌우로 문(간선)이 있다고 상상해봅시다. 만약 간선이 서로 연결되어 있으면 문이 열릴 것이고, 간선이 서로 연결되어 있지 않으면 문이 닫혀있겠죠

여기서 값이 1인 배추가 상하좌우로 인접한 경우에만 이어져 있다고 합니다. 그래서 연결된 배추끼리 그림으로 구별해보면 아래 그림과 같습니다.

이렇게 색칠을 하여 총 5마리의 애벌레를 필요로 하다는 것을 알 수 있습니다.

코드로 색깔을 나눠서 구분할 수 없으니까 우리는 모든 값이 0으로 되어 있는 똑같은 크기의 배열을 새로 하나 만들어서 거기에 숫자를 부여할 겁니다.

이러면 애벌레의 수를 바로 출력할 수 있겠네요.

이것을 어떻게 구현하는지 바로 문제를 풀어보면서 알아봅시다.

연습 문제

BOJ 1012 - BFS

1012번: 유기농 배추Baekjoon Online Judge

배추 흰 지렁이가 최소 몇 마리 필요한지 구하는 문제입니다. 예제 1은 위에서 이미 5마리라고 설명했습니다.

바로 입력값을 받는 코드를 짜봅시다.

가로 길이 M, 세로 길이가 N이므로 모든 값이 0인 N x M 2차원 배열을 만들어주고, K개의 배추의 위치를 입력받아 해당 위치의 값을 1로 변경해줍니다. 그리고 배추의 입력을 받을 때, (가로 위치, 세로 위치)로 주어지므로 주의해야 합니다.

t = int(input())
for ___ in range(t):
    m, n, k = map(int,input().split())
    arr = [[0]*m for _ in range(n)]
    for i in range(k):
        y, x = map(int,input().split())
        arr[x][y] = 1

이제 구역을 구분할 배열을 똑같은 크기로 만들어줍시다. 여기서도 처음엔 모든 값이 0입니다. 이름은 check라고 하겠습니다. 그리고 플러드 필을 할 때, 우리는 check에 숫자를 부여할 것이므로 val = 1이라는 변수를 추가해줍니다.

t = int(input())
for ___ in range(t):
    m, n, k = map(int,input().split())
    arr = [[0]*m for _ in range(n)]
    for i in range(k):
        y, x = map(int,input().split())
        arr[x][y] = 1
    check = [[0]*m for _ in range(n)]
    val = 1

이제 2중 for문을 이용하여 배열을 하나씩 방문해봅니다. 이때 해당 위치가 배추가 있는 곳인데, 아직 방문하지 않은 노드면 플러드 필을 시작하고, 이미 방문한 노드면 그대로 지나가면 됩니다.

t = int(input())
for ___ in range(t):
    m, n, k = map(int,input().split())
    arr = [[0]*m for _ in range(n)]
    for i in range(k):
        y, x = map(int,input().split())
        arr[x][y] = 1
    check = [[0]*m for _ in range(n)]
    val = 1

    for i in range(n):
        for j in range(m):
            if check[i][j] == 0 and arr[i][j] == 1:
                플러드필 시작

플러드 필을 하는 방법은 BFS와 DFS 2가지 방법으로 할 수 있습니다. 이 문제에서는 BFS로 풀어보겠습니다.

먼저 BFS로 풀려면 큐가 필요하므로 collections.deque를 불러오고 큐를 만들어줍니다.

from collections import deque # 추

t = int(input())
for ___ in range(t):
    m, n, k = map(int,input().split())
    arr = [[0]*m for _ in range(n)]
    for i in range(k):
        y, x = map(int,input().split())
        arr[x][y] = 1
    check = [[0]*m for _ in range(n)]
    val = 1
    
    q = deque() # 추가
    for i in range(n):
        for j in range(m):
            if check[i][j] == 0 and arr[i][j] == 1: 플러드필 시작

이제 플러드 필을 시작하는 부분에서 큐에 (i, j)를 넣어주면 됩니다.

from collections import deque

t = int(input())
for ___ in range(t):
    m, n, k = map(int,input().split())
    arr = [[0]*m for _ in range(n)]
    for i in range(k):
        y, x = map(int,input().split())
        arr[x][y] = 1
    check = [[0]*m for _ in range(n)]
    val = 1

    q = deque()
    for i in range(n):
        for j in range(m):
            if check[i][j] == 0 and arr[i][j] == 1:
                check[i][j] = val
                q.append((i,j)) # 추가

check[i][j] = val로 색칠을 해주고, 이제 while문을 추가하여 큐에 더 이상 원소가 없을 때까지 확인하면 됩니다. C++의 경우에는 while(!q.empty())를 적어주면 됩니다.

from collections import deque

t = int(input())
for ___ in range(t):
    m, n, k = map(int,input().split())
    arr = [[0]*m for _ in range(n)]
    for i in range(k):
        y, x = map(int,input().split())
        arr[x][y] = 1
    check = [[0]*m for _ in range(n)]
    val = 1

    q = deque()
    for i in range(n):
        for j in range(m):
            if check[i][j] == 0 and arr[i][j] == 1:
                check[i][j] = val
                q.append((i,j))
                while q: # 추가
                    blah blah # 추가

이제 q에 좌표를 뽑아냅니다.

from collections import deque

t = int(input())
for ___ in range(t):
    m, n, k = map(int,input().split())
    arr = [[0]*m for _ in range(n)]
    for i in range(k):
        y, x = map(int,input().split())
        arr[x][y] = 1
    check = [[0]*m for _ in range(n)]
    val = 1

    q = deque()
    for i in range(n):
        for j in range(m):
            if check[i][j] == 0 and arr[i][j] == 1:
                check[i][j] = val
                q.append((i,j))
                while q:
                    x, y = q.popleft() # 추가

그리고 이제 상하좌우로 움직여야 합니다.

(x, y)가 있을 때, 위로 움직이면 (x-1, y)가 되고, 아래는 (x+1, y)가 됩니다. 왼쪽으로 움직이면 (x, y-1)이 되고, 오른쪽으로 움직이면 (x, y+1)이 됩니다.

2차원 리스트니까 왜 이렇게 움직이는지 이해하실 수 있을 겁니다.

그래서 코드에서 상하좌우로 움직이는 코드를 추가해야 합니다.

from collections import deque
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1] # 상하좌우

t = int(input())
for ___ in range(t):
    m, n, k = map(int,input().split())
    arr = [[0]*m for _ in range(n)]
    for i in range(k):
        y, x = map(int,input().split())
        arr[x][y] = 1
    check = [[0]*m for _ in range(n)]
    val = 1

    q = deque()
    for i in range(n):
        for j in range(m):
            if check[i][j] == 0 and arr[i][j] == 1:
                check[i][j] = val
                q.append((i,j))
                while q:
                    x, y = q.popleft()

코드가 너무 길어서 while문만 따로 떼어서 보겠습니다.

while q:
    x, y = q.popleft()

여기서 이제 상하좌우로 움직여야하므로 for문을 이용하여 dx, dy를 더하는 방식으로 사용할 수 있습니다.

while q:
    x, y = q.popleft()
    for k in range(4):
        nx, ny = x + dx[k], y + dy[k]

이제 nx와 ny가 n x m 배열 범위에 속하는지, 배추가 있는 곳인지, 아직 색칠하지 않은 곳인지 확인하는 조건문을 추가합니다.

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: #n x m 배열 범위에 속하는지
            if arr[nx][ny] == 1: # 배추가 있는 곳인지
                if check[nx][ny] == 0: # 아직 색칠하지 않은 곳인지
                     blah blah

먼저 첫 번째 조건문은 만약 (0, 0)이 배추라면 상하좌우로 이동할 경우 각각의 좌표는 (-1, 0), (1, 0), (0, -1), (0, 1)이 될 것입니다. 그런데 (-1, 0)과 (0, -1)의 경우에는 2차원 배열에 속하지 않은 좌표니까 걸러줘야 합니다.

두 번째 조건과 세 번째 조건은 우리가 배추가 있는 곳에서만 색칠을 하는 것이므로 필요한 조건문입니다.

이렇게 3개의 조건문으로 거른 좌표는 색칠을 해야 하는 배추가 됩니다. 그래서 여기 check[nx][ny] 에 val 값을 저장해주고, 큐에 (nx, ny)를 넣어주면 됩니다.

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:
            if arr[nx][ny] == 1:
                if check[nx][ny] == 0:
                     check[nx][ny] = val
                     q.append((nx,ny))

이것을 그대로 원래 코드에 넣어주면 됩니다.

참고로 arr[nx][ny] == 1이라는 것은 True라는 것이고, check[nx][ny] == 0은 False라는 것이므로 조금 더 간단하게 조건문을 표현할 수 있습니다.

from collections import deque
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1] # 상하좌우

t = int(input())
for ___ in range(t):
    m, n, k = map(int,input().split())
    arr = [[0]*m for _ in range(n)]
    for i in range(k):
        y, x = map(int,input().split())
        arr[x][y] = 1
    check = [[0]*m for _ in range(n)]
    val = 1

    q = deque()
    for i in range(n):
        for j in range(m):
            if check[i][j] == 0 and arr[i][j] == 1:
                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]:
                            check[nx][ny] = val
                            q.append((nx,ny))

이제 while문이 끝났으면 서로 연결된 배추의 색칠이 끝났다는 것입니다.

이렇게 아직 색칠되어있지 않으면 while문이 끝날 때마다 하나씩 색칠이 된다는 것입니다.

우리는 숫자를 통해 색칠하므로 1번 구역의 색칠이 모두 끝났으니, 이제 val 에 1을 더해주어서 다음에 아직 색칠되지 않은 배추를 만나면 2번 구역으로 설정해주면 됩니다.

from collections import deque
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1] # 상하좌우

t = int(input())
for ___ in range(t):
    m, n, k = map(int,input().split())
    arr = [[0]*m for _ in range(n)]
    for i in range(k):
        y, x = map(int,input().split())
        arr[x][y] = 1
    check = [[0]*m for _ in range(n)]
    val = 1

    q = deque()
    for i in range(n):
        for j in range(m):
            if check[i][j] == 0 and arr[i][j] == 1:
                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]:
                            check[nx][ny] = val
                            q.append((nx,ny))
                val += 1 # 추가

이렇게 되어서 코드가 끝나게 되면 val의 값은 6이 됩니다. 그래서 답을 출력할 때는 val - 1을 출력하면 됩니다.

from collections import deque
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1] # 상하좌우

t = int(input())
for ___ in range(t):
    m, n, k = map(int,input().split())
    arr = [[0]*m for _ in range(n)]
    for i in range(k):
        y, x = map(int,input().split())
        arr[x][y] = 1
    check = [[0]*m for _ in range(n)]
    val = 1

    q = deque()
    for i in range(n):
        for j in range(m):
            if check[i][j] == 0 and arr[i][j] == 1:
                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]:
                            check[nx][ny] = val
                            q.append((nx,ny))
    print(val - 1)

코드가 한 번에 보이지 않아서 18줄 ~ 25줄을 따로 함수를 선언하여 만들어보겠습니다.

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:
                if arr[nx][ny] and not check[nx][ny]:
                    check[nx][ny] = val
                    q.append((nx, ny))

from collections import deque
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1] # 상하좌우

t = int(input())
for ___ in range(t):
    m, n, k = map(int,input().split())
    arr = [[0]*m for _ in range(n)]
    for i in range(k):
        y, x = map(int,input().split())
        arr[x][y] = 1
    check = [[0]*m for _ in range(n)]
    val = 1

    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)

BOJ 1743 - DFS

1743번: 음식물 피하기Baekjoon Online Judge

플러드 필을 하면서 가장 큰 음식물의 크기를 출력하라고 합니다. 이번엔 DFS로 풀어보겠습니다.

BOJ 1012 문제랑 똑같이 상하좌우로 움직이는 dx, dy 배열을 추가해주고 입력값을 받아봅시다.

세로 길이 N, 가로 길이 M이므로 모든 값이 0인 N x M 2차원 배열을 만들어주고, 음식물이 있는 곳의 값은 1로 변경합니다. 이번에는 (0, 0)이 (1, 1)로 입력되고 있으므로 값을 1씩 빼서 배열의 값을 1로 변경하면 됩니다.

dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1] # 상하좌우

n, m, k = map(int,input().split())
arr = [[0]*m for _ in range(n)]
for i in range(k):
    x, y = map(int,input().split())
    arr[x-1][y-1] = 1

이것도 색칠을 해야 하는데 마찬가지로 모든 값이 0인 check 배열을 만들어주고, 값을 출력할 ans 변수도 만들어주면 됩니다.

dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1] # 상하좌우
n, m, k = map(int,input().split())
arr = [[0]*m for _ in range(n)]
for i in range(k):
    x, y = map(int,input().split())
    arr[x-1][y-1] = 1
check = [[0]*m for _ in range(n)]
ans = 0

이번엔 재귀 함수로 풀려고 하는데, 2중 for문을 이용하여 해당 위치가 음식물이 있는 위치인지, 아직 방문하지 않은 위치인지 확인해주면 됩니다.

dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1] # 상하좌우
n, m, k = map(int,input().split())
arr = [[0]*m for _ in range(n)]
for i in range(k):
    x, y = map(int,input().split())
    arr[x-1][y-1] = 1
check = [[0]*m for _ in range(n)]
ans = 0
for i in range(n):
    for j in range(m):
        if arr[i][j] == 1 and check[i][j] == 0:
            blah blah

이제 우리는 재귀 함수를 구현해야 합니다. 그리고 음식물 쓰레기의 크기를 구해야 하는데, 11줄의 조건문을 통과하는 음식물은 무조건 색칠해야 하는 음식물이므로 res = 1을 선언하여 처음 음식물의 크기를 1로 설정하고, check[i][j] = 1로 색칠을 해주면 됩니다. 다른 음식물들도 전부 1로 값을 넣어주면 됩니다.

여기서 BOJ 1012와 다르게 check[nx][ny] = 1로 색칠하는 이유는 음식물의 개수를 구하라는 문제가 아니기 때문에 단순히 색칠 했냐/색칠하지 않았냐로 1과 0으로 표현해도 됩니다. BOJ 1012처럼 음식물에 숫자를 부여해도 상관없긴 합니다. 그런데 그러면 코드가 더 추가되겠지요.

재귀 함수 이름은 flood_fill()이라고 하고, 인자는 현재 위치의 좌표를 넣어줍니다. 음식물을 발견할 때마다 res에 1을 더해서 음식물의 크기를 구해야 하니 global 키워드를 추가해야 합니다.

def flood_fill(x, y):
    global res
    blah blah

dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1] # 상하좌우
n, m, k = map(int,input().split())
arr = [[0]*m for _ in range(n)]
for i in range(k):
    x, y = map(int,input().split())
    arr[x-1][y-1] = 1
check = [[0]*m for _ in range(n)]
ans = 0
for i in range(n):
    for j in range(m):
        if arr[i][j] == 1 and check[i][j] == 0:
            res = 1
            check[i][j] = 1
            flood_fill(i, j)

flood_fill()함수도 BFS와 마찬가지 조건으로 범위 내에 있는 위치인지, 음식물이 있는 곳인지, 색칠되어 있지 않은 곳인지 확인하면 됩니다.

def flood_fill(x, y):
    global res
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx < n and 0 <= ny < m:
            if arr[nx][ny] and not check[nx][ny]:
                blah blah

dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1] # 상하좌우
n, m, k = map(int,input().split())
arr = [[0]*m for _ in range(n)]
for i in range(k):
    x, y = map(int,input().split())
    arr[x-1][y-1] = 1
check = [[0]*m for _ in range(n)]
ans = 0
for i in range(n):
    for j in range(m):
        if arr[i][j] == 1 and check[i][j] == 0:
            res = 1
            check[i][j] = 1
            flood_fill(i, j)

이 조건문에 해당하는 위치는 색칠해야 할 음식물이므로 res += 1을 해주고, check[nx][ny] = 1로 색칠을 해주고, flood_fill(nx, ny)를 해주면 됩니다.

def flood_fill(x, y):
    global res
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx < n and 0 <= ny < m:
            if arr[nx][ny] and not check[nx][ny]:
                res += 1
                check[nx][ny] = 1
                flood_fill(nx,ny)

dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1] # 상하좌우
n, m, k = map(int,input().split())
arr = [[0]*m for _ in range(n)]
for i in range(k):
    x, y = map(int,input().split())
    arr[x-1][y-1] = 1
check = [[0]*m for _ in range(n)]
ans = 0
for i in range(n):
    for j in range(m):
        if arr[i][j] == 1 and check[i][j] == 0:
            res = 1
            check[i][j] = 1
            flood_fill(i, j)

재귀 함수를 실행하면 res의 값이 바뀌어 있을 겁니다. 이제 우리가 처음에 선언한 ans의 값을 ans와 res중 큰 수로 업데이트하고, ans를 출력하면 됩니다.

그리고 최대 100x100 크기의 배열이 만들어지므로 재귀 깊이가 1000이 넘어갑니다. 그래서 sys.setrecursionlimit(10000)으로 설정해야 합니다.

def flood_fill(x, y):
    global res
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx < n and 0 <= ny < m:
            if arr[nx][ny] and not check[nx][ny]:
                res += 1
                check[nx][ny] = 1
                flood_fill(nx,ny)

import sys
sys.setrecursionlimit(10000)
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1] # 상하좌우
n, m, k = map(int,input().split())
arr = [[0]*m for _ in range(n)]
for i in range(k):
    x, y = map(int,input().split())
    arr[x-1][y-1] = 1
check = [[0]*m for _ in range(n)]
ans = 0
for i in range(n):
    for j in range(m):
        if arr[i][j] == 1 and check[i][j] == 0:
            res = 1
            check[i][j] = 1
            flood_fill(i, j)
            ans = max(ans, res)
print(ans)

플러드 필

연습 문제

BOJ 1012 - BFS

BOJ 1743 - DFS

풀어볼 문제