> For the complete documentation index, see [llms.txt](https://70825.gitbook.io/python-study/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://70825.gitbook.io/python-study/9/9-3.md).

# 플러드 필

시뮬레이션

* [x] [2차원 리스트](https://70825.gitbook.io/python-study/6/6-1)
* [x] [자주 사용하는 모듈](https://70825.gitbook.io/python-study/6/6-3)
* [x] [순열과 조합](https://70825.gitbook.io/python-study/7/7-2)
* [x] [재귀 함수 Ⅰ](https://70825.gitbook.io/python-study/8/8-3)
* [x] [재귀 함수 Ⅱ](https://70825.gitbook.io/python-study/9/9-1)
* [x] [그래프 알고리즘 소개](https://70825.gitbook.io/python-study/9/9-2)
* [x] 플러드 필 - 현재 글
* [ ] 시뮬레이션 Ⅰ
* [ ] 시뮬레이션 Ⅱ

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

## 플러드 필

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

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

{% embed url="<https://www.acmicpc.net/problem/1012>" %}

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

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

![](/files/-MZrxb_9pGPuKMaX2N3B)

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

![](/files/-MZrxdF0_f5JUzoeJg7n)

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

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

![](/files/-MZrxf1ZROsELZgJuu3E)

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

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

## 연습 문제

### BOJ 1012 - BFS

{% embed url="<https://www.acmicpc.net/problem/1012>" %}

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

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

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

```python
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이라는 변수를 추가해줍니다.

```python
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문을 이용하여 배열을 하나씩 방문해봅니다. 이때 해당 위치가 배추가 있는 곳인데, 아직 방문하지 않은 노드면 플러드 필을 시작하고, 이미 방문한 노드면 그대로 지나가면 됩니다.

```python
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를 불러오고 큐를 만들어줍니다.

```python
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)를 넣어주면 됩니다.

```python
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())를 적어주면 됩니다.

```python
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에 좌표를 뽑아냅니다.

```python
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)이 됩니다.

![](/files/-MZrxi9K3OR-MnW5LP1c)

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

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

```python
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문만 따로 떼어서 보겠습니다.

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

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

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

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

```python
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)를 넣어주면 됩니다.

```python
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라는 것이므로 조금 더 간단하게 조건문을 표현할 수 있습니다.

```python
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문이 끝났으면 서로 연결된 배추의 색칠이 끝났다는 것입니다.

![](/files/-MZrxkWqlPkQ2uTVX6DM)

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

![](/files/-MZrxmLNqz6obeJmaOQ5)

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

```python
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 # 추가
```

![](/files/-MZrxo-h1SN3T5nk0li_)

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

```python
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줄을 따로 함수를 선언하여 만들어보겠습니다.

```python
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

{% embed url="<https://www.acmicpc.net/problem/1743>" %}

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

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

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

```python
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 변수도 만들어주면 됩니다.

```python
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문을 이용하여 해당 위치가 음식물이 있는 위치인지, 아직 방문하지 않은 위치인지 확인해주면 됩니다.

```python
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 키워드를 추가해야 합니다.

```python
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와 마찬가지 조건으로 범위 내에 있는 위치인지, 음식물이 있는 곳인지, 색칠되어 있지 않은 곳인지 확인하면 됩니다.

```python
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)를 해주면 됩니다.

```python
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)으로 설정해야 합니다.

```python
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)
```

## 풀어볼 문제

* <https://www.acmicpc.net/problem/1926>
* <https://www.acmicpc.net/problem/10026>
* <https://www.acmicpc.net/problem/3184>
* <https://www.acmicpc.net/problem/15240>
* <https://www.acmicpc.net/problem/15092>