Live of Thinking

그리드(격자, Grid)는 특수한 형태의 그래프로, $n$차원 좌표공간에 존재하는 점으로 표현되는 정점들과 정점들 사이를 잇는 간선으로 이루어져 있다. $n$은 대체로 $2$이며 가끔씩 $n$이 다른 값인 문제도 존재한다. 또한 점 대신 칸으로 이루어진 그리드가 등장하는 경우도 많은데, 각 칸을 그 중심점으로 바꾸면 정점과 간선으로 이루어진 그리드로 쉽게 변환이 가능하므로 이것은 별로 문제가 되지 않는다. 그리드의 좌표를 인덱스(Index)라고 하는 경우도 많다.

그리드에서 정점 사이를 잇는 간선은 보통 서로 인접한 칸들 사이에는 모두 존재한다. 일반적으로 그리드에서 두 칸이 인접하다는 것은 이렇게 이해할 수 있다: 정점 $\text{A}$의 좌표가 $(a_1, a_2, \ldots, a_n)$이고 정점 $\text{B}$의 좌표가 $(b_1, b_2, \ldots, b_n)$일 때, $\text{A}$와 $\text{B}$가 인접할 경우 다음 식이 성립한다.

$$|a_1 - b_1| + |a_2 - b_2| + \ldots + |a_n - b_n| = 1$$

이 식의 좌변을 보면 각각의 항이 절댓값으로 더해지고 모든 좌표는 정수로 표현되므로 $(n - 1)$개의 항이 $0$이고 나머지 한 항이 $1$일 때만 식이 성립한다는 것을 확인할 수 있다.

어떤 문제에서는 대각선 방향에 존재하는 칸들 사이에도 간선이 있는데, 이것 역시 식으로 이해할 수 있다. 인접한 정점과 대각선 방향에 있는 정점들 사이에 간선이 존재하는 그리드의 정점 $\text{A}$와 정점 $\text{B}$ 사이에 간선이 존재할 경우 다음 식이 성립한다.

$$\max(|a_1 - b_1|, |a_2 - b_2|, \ldots, |a_n - b_n|) = 1$$

물론 $n$이 $3$ 이상일 경우 대각선 방향이라는 표현이 모호해지기 때문에 $3$차원 이상의 그리드에서는 이런 표현이 잘 사용되지 않는다.

대부분의 문제는 그리드의 좌표 범위에 제한이 있다. 일반적으로 모든 축의 좌표가 $0$ 이상의 정수인 범위로 제한되는 그리드가 주어지는 경우가 많지만 가끔씩 그렇지 않은 경우도 있으며 이때는 음수 좌표의 처리를 편하게 하기 위해서 모든 좌표에 일정한 오프셋(Offset)을 더해서 좌표가 음수가 되지 않게 만든 뒤 문제를 푸는 경우가 많다.

플러드 필(Flood Fill)^[각주:1]은 그리드에서 실행되는 탐색 방법으로, 어떤 칸과 연결된 영역을 DFS나 BFS로 찾는다. 원리는 기본 DFS, BFS와 크게 다르지 않다. 일반적으로 영역 자체만을 구할 경우는 DFS를 사용하는 것이 조금 더 편하며, BFS가 강제되는 경우 BFS를 사용하면 된다.

플러드 필이 일반 DFS, BFS와 차이를 보이는 부분은 구현이다. 일반 DFS, BFS와 달리 플러드 필에서는 어떤 정점 사이에 간선이 존재하는지가 기본적으로 정의되어 있으므로 인접 행렬이나 인접 리스트 등에 간선 정보를 저장할 필요가 없고, 재귀호출을 하는 부분도 조금 달라진다. DFS를 사용하는 경우의 가장 간단한 구현은 대충 다음과 같다.

#import<bits/stdc++.h>
using namespace std;
int m, n, a[1005][1005];
void flood_fill(int x, int y)
{
    if(x < 1 || x > n || y < 1 || y > m || a[x][y])return;
    a[x][y] = 1;
    flood_fill(x - 1, y);
    flood_fill(x, y - 1);
    flood_fill(x, y + 1);
    flood_fill(x + 1, y);
}
int main()
{
    int x, y;
    cin >> n >> m >> x >> y;
    flood_fill(x, y); // Flood Fill 시작 정점
}

위 코드를 실행하면 칸 $(x, y)$에서 플러드 필을 시작해서 $n \times m$ 크기의 그리드의 각 칸을 $1$로 채운다. flood_fill 함수 안에는 가장 기본적인 세 가지 요소가 포함되어 있다.

더 탐색하지 않는 경우에 대한 조건: 인덱스가 그리드의 범위를 벗어났거나, 이미 방문한 칸을 다시 방문했을 경우 이 칸에서 더 탐색하지 않고 되돌아간다. 위 코드에는 존재하지 않지만, 어떤 조건에 의해 이동할 수 없는 칸을 방문했을 경우도 탐색하지 않고 되돌아가야 한다.
방문 체크: 더 탐색을 하는 경우, 이 칸을 방문했다는 것을 체크하고 넘어간다.
인접한 칸으로의 재귀호출: 인접한 칸들을 재귀적으로 탐색한다.

$2$차원 그리드에서 위 코드와 같이 상하좌우로 인접한 $4$칸이 서로 연결되는 방식을 $4$방향 연결(${\color{#FF0000}4}$-Connectivity)이라고 하고 이 방식으로 탐색을 진행하는 것을 $4$방향 탐색(${\color{#FF0000}4}$-Way Search)이라고 한다. 어떤 $2$차원 그리드는 대각선으로도 서로 연결이 되는데, 이 방식을 $8$방향 연결(${\color{#FF0000}8}$-Connectivity)이라고 하고 이 방식으로 탐색을 진행하는 것을 $8$방향 탐색(${\color{#FF0000}8}$-Way Search)이라고 한다. $8$방향 탐색을 하는 경우 아래와 같이 재귀호출을 $8$번 할 수도 있고,

#import<bits/stdc++.h>
using namespace std;
int m, n, a[1005][1005];
void flood_fill(int x, int y)
{
    if(x < 1 || x > n || y < 1 || y > m || a[x][y])return;
    a[x][y] = 1;
    flood_fill(x - 1, y - 1);
    flood_fill(x - 1, y);
    flood_fill(x - 1, y + 1);
    flood_fill(x, y - 1);
    flood_fill(x, y + 1);
    flood_fill(x + 1, y - 1);
    flood_fill(x + 1, y);
    flood_fill(x + 1, y + 1);
}
int main()
{
    int x, y;
    cin >> n >> m >> x >> y;
    flood_fill(x, y); // Flood Fill 시작 정점
}

코드가 길어지는 것을 방지하기 위해서 다음과 같이 작성하기도 한다.

#import<bits/stdc++.h>
using namespace std;
int m, n, dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1}, dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1}, a[1005][1005];
void flood_fill(int x, int y)
{
    if(x < 1 || x > n || y < 1 || y > m || a[x][y])return;
    a[x][y] = 1;
    for(int i = 0; i < 8; i++)flood_fill(x + dx[i], y + dy[i]);
}
int main()
{
    int x, y;
    cin >> n >> m >> x >> y;
    flood_fill(x, y); // Flood Fill 시작 정점
}

========================================================================================================================

#import<bits/stdc++.h>
using namespace std;
int m, n, dx[3] = {-1, 0, 1}, dy[3] = {-1, 0, 1}, a[1005][1005];
void flood_fill(int x, int y)
{
    if(x < 1 || x > n || y < 1 || y > m || a[x][y])return;
    a[x][y] = 1;
    for(int i = 0; i < 3; i++)
    {
        for(int j = 0; j < 3; j++)
        {
            if(i != 1 || j != 1)flood_fill(x + dx[i], y + dy[j]); // if문은 생략할 수 있음
        }
    }
}
int main()
{
    int x, y;
    cin >> n >> m >> x >> y;
    flood_fill(x, y); // Flood Fill 시작 정점
}

위의 마지막 코드를 BFS를 사용하는 방식으로 바꾸면 대략 다음과 같이 된다.

#import<bits/stdc++.h>
using namespace std;
int dx[3] = {-1, 0, 1}, dy[3] = {-1, 0, 1}, a[1005][1005];
queue<pair<int, int>>Q;
int main()
{
    int m, n, tx, ty, x, y;
    cin >> n >> m >> x >> y;
    a[x][y] = 1;
    for(Q.push({x, y}; Q.size(); Q.pop())
    {
        x = Q.front().first;
        y = Q.front().second;
        for(int i = 0; i < 3; i++)
        {
            for(int j = 0; j < 3; j++)
            {
                tx = x + dx[i];
                ty = y + dy[j];
                if(0 < tx && tx <= n && 0 < ty && ty <= m && !a[tx][ty])
                {
                    a[tx][ty] = 1;
                    Q.push({tx, ty});
                }
            }
        }
    }
}

BFS를 사용해서 구현할 때는 같은 칸이 큐에 여러 번 들어가지 않게 하는 것이 중요하다. 일반적인 그래프에서 BFS를 구현할 때에 비해 플러드 필을 BFS로 구현할 때 이 실수가 발생하기 쉽다. 이런 이유로 칸이 큐에 들어가는 시점에 그 칸의 방문 체크를 한다.

[연습문제: DFS, BFS 모두 사용이 가능한 경우]

113. Diameter of Tree (0)	2021.12.29
112. Bipartite Graph (0)	2021.12.27
110. Breadth First Search (0)	2021.12.22
109. Depth First Search (0)	2021.11.19
108. Postorder Traversal (0)	2021.11.17

111. Grid & Flood Fill

'Algorithm > H. Trees & Graphs' 카테고리의 다른 글

'Algorithm/H. Trees & Graphs' Related Articles

티스토리툴바