[알고리즘] 31. 격자 탐색
지난 글에서는 방문 배열에 대해 정리했습니다. 이번 글에서는 2차원 배열에서 상하좌우로 이동하며 탐색하는 격자 탐색에 대해 알아보겠습니다.
격자 탐색은 알고리즘 문제에서 매우 자주 등장합니다. 미로 찾기, 섬의 개수, 영역 구하기, 바이러스 전파, 토마토 익히기 같은 문제들이 대부분 격자 탐색과 연결됩니다.
격자 탐색은 2차원 배열에서 현재 위치를 기준으로 상하좌우 또는 대각선 방향을 확인하며 이동하는 탐색 방식입니다.
1. 격자 탐색이란?
격자는 행과 열로 이루어진 2차원 구조입니다. 알고리즘 문제에서는 보통 2차원 배열로 표현합니다.
1 1 0
0 1 0
1 1 1위와 같은 구조에서 각 칸은 하나의 위치를 의미합니다. 예를 들어 1은 이동 가능한 칸, 0은 이동할 수 없는 칸이라고 생각할 수 있습니다.
격자 탐색은 특정 위치에서 시작해 상하좌우로 이동하면서 조건에 맞는 칸을 방문하는 방식입니다.
격자 탐색은 2차원 배열을 그래프처럼 보고, 칸과 칸 사이를 이동하는 탐색입니다.
2. 행과 열 이해하기
2차원 배열에서는 위치를 보통 행(row)과 열(column)로 표현합니다. Java에서는 arr[x][y] 또는 arr[row][col] 형태로 접근합니다.
| 표현 | 의미 |
|---|---|
| x 또는 row | 행 번호 |
| y 또는 col | 열 번호 |
예를 들어 아래 배열을 보겠습니다.
인덱스:
(0,0) (0,1) (0,2)
(1,0) (1,1) (1,2)
(2,0) (2,1) (2,2)왼쪽 위 칸은 (0, 0)이고, 오른쪽 아래 칸은 (2, 2)입니다. 배열의 인덱스는 0부터 시작한다는 점을 기억해야 합니다.
3. 상하좌우 이동
격자 탐색에서는 현재 위치에서 상하좌우로 이동하는 경우가 많습니다. 현재 위치가 (x, y)라면 상하좌우 위치는 다음과 같습니다.
| 방향 | 이동 후 위치 |
|---|---|
| 위 | (x - 1, y) |
| 아래 | (x + 1, y) |
| 왼쪽 | (x, y - 1) |
| 오른쪽 | (x, y + 1) |
이동 방향을 매번 직접 작성하면 코드가 길어집니다. 그래서 보통 방향 배열을 사용합니다.
int[] dx = {-1, 1, 0, 0};
int[] dy = {0, 0, -1, 1};dx와 dy를 함께 사용하면 상, 하, 좌, 우 네 방향을 반복문으로 처리할 수 있습니다.
격자 탐색의 핵심 도구는 dx, dy 방향 배열입니다.
4. 방향 배열 사용하기
현재 위치가 (x, y)일 때, 네 방향의 다음 위치는 다음처럼 구할 수 있습니다.
int x = 1;
int y = 1;
int[] dx = {-1, 1, 0, 0};
int[] dy = {0, 0, -1, 1};
for (int dir = 0; dir < 4; dir++) {
int nx = x + dx[dir];
int ny = y + dy[dir];
System.out.println(nx + " " + ny);
}출력 결과는 다음과 같습니다.
0 1
2 1
1 0
1 2현재 위치 (1, 1)을 기준으로 위, 아래, 왼쪽, 오른쪽 위치가 차례대로 계산됩니다.
5. 범위 체크가 중요한 이유
격자 탐색에서 가장 중요한 것은 범위 체크입니다. 2차원 배열 밖으로 나가면 인덱스 오류가 발생합니다.
예를 들어 3행 3열 배열에서 사용할 수 있는 인덱스는 다음과 같습니다.
행 인덱스: 0, 1, 2
열 인덱스: 0, 1, 2만약 x가 -1이 되거나, y가 3이 되면 배열 범위를 벗어납니다. 따라서 다음 위치를 계산한 뒤에는 반드시 범위 안에 있는지 확인해야 합니다.
if (nx < 0 || ny < 0 || nx >= n || ny >= m) {
continue;
}격자 탐색에서는 배열에 접근하기 전에 반드시 범위 체크를 해야 합니다.
6. 격자 탐색의 기본 체크 순서
격자 탐색에서는 다음 위치를 확인할 때 보통 아래 순서를 사용합니다.
- 다음 위치 nx, ny를 계산한다.
- 배열 범위를 벗어났는지 확인한다.
- 이미 방문한 위치인지 확인한다.
- 이동 가능한 칸인지 확인한다.
- 조건을 만족하면 방문 처리 후 이동한다.
다음 위치 계산
→ 범위 체크
→ 방문 체크
→ 이동 가능 여부 체크
→ 방문 처리이 순서가 중요한 이유는 범위를 벗어난 위치에 대해 visited[nx][ny]나 map[nx][ny]를 먼저 확인하면 오류가 발생하기 때문입니다.
범위 체크는 visited나 map 배열 접근보다 먼저 해야 합니다.
7. 2차원 DFS 기본 코드
격자 탐색은 DFS로 구현할 수 있습니다. 현재 위치에서 갈 수 있는 곳까지 깊게 들어가는 방식입니다.
static int[][] map;
static boolean[][] visited;
static int n;
static int m;
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
public static void dfs(int x, int y) {
visited[x][y] = true;
for (int dir = 0; dir < 4; dir++) {
int nx = x + dx[dir];
int ny = y + dy[dir];
if (nx < 0 || ny < 0 || nx >= n || ny >= m) {
continue;
}
if (visited[nx][ny]) {
continue;
}
if (map[nx][ny] == 0) {
continue;
}
dfs(nx, ny);
}
}이 코드는 현재 위치에서 상하좌우를 확인하고, 방문하지 않았으며 이동 가능한 칸이면 재귀적으로 DFS를 수행합니다.
8. 2차원 BFS 기본 코드
격자 탐색은 BFS로도 구현할 수 있습니다. BFS는 가까운 칸부터 차례대로 탐색하므로 최단 거리 문제에 자주 사용됩니다.
import java.util.LinkedList;
import java.util.Queue;
public static void bfs(int startX, int startY) {
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[] {startX, startY});
visited[startX][startY] = true;
while (!queue.isEmpty()) {
int[] current = queue.poll();
int x = current[0];
int y = current[1];
for (int dir = 0; dir < 4; dir++) {
int nx = x + dx[dir];
int ny = y + dy[dir];
if (nx < 0 || ny < 0 || nx >= n || ny >= m) {
continue;
}
if (visited[nx][ny]) {
continue;
}
if (map[nx][ny] == 0) {
continue;
}
visited[nx][ny] = true;
queue.offer(new int[] {nx, ny});
}
}
}BFS에서는 큐에 넣는 순간 방문 처리하는 것이 안전합니다. 그래야 같은 칸이 큐에 여러 번 들어가는 일을 막을 수 있습니다.
격자 최단 거리 문제에서는 보통 BFS를 먼저 떠올리면 좋습니다.
9. 격자에서 영역 개수 세기
격자 탐색의 대표 문제는 연결된 영역의 개수를 세는 것입니다. 예를 들어 1은 땅, 0은 바다라고 생각해보겠습니다.
1 1 0
0 1 0
1 0 1상하좌우로 연결된 1들을 하나의 영역으로 보면, 위 격자에는 여러 개의 영역이 존재합니다.
영역 개수는 모든 칸을 확인하면서, 아직 방문하지 않은 1을 발견할 때마다 DFS 또는 BFS를 시작하면 구할 수 있습니다.
int count = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (map[i][j] == 1 && !visited[i][j]) {
dfs(i, j);
count++;
}
}
}
System.out.println(count);새로운 DFS가 시작될 때마다 새로운 영역을 발견한 것입니다.
격자에서 영역 개수는 방문하지 않은 시작점을 몇 번 발견하는지로 셀 수 있습니다.
10. 영역 크기 구하기
영역의 개수뿐 아니라 각 영역의 크기를 구해야 하는 문제도 있습니다. 이때는 DFS나 BFS를 하면서 방문한 칸 수를 세면 됩니다.
public static int dfsSize(int x, int y) {
visited[x][y] = true;
int size = 1;
for (int dir = 0; dir < 4; dir++) {
int nx = x + dx[dir];
int ny = y + dy[dir];
if (nx < 0 || ny < 0 || nx >= n || ny >= m) {
continue;
}
if (visited[nx][ny]) {
continue;
}
if (map[nx][ny] == 0) {
continue;
}
size += dfsSize(nx, ny);
}
return size;
}현재 칸을 방문했으므로 size를 1로 시작합니다. 그다음 연결된 칸의 크기를 더하면서 전체 영역 크기를 계산합니다.
11. 격자 최단 거리 구하기
격자에서 시작점부터 목적지까지의 최소 이동 횟수를 구하는 문제는 BFS가 잘 어울립니다. BFS는 가까운 칸부터 차례대로 방문하기 때문입니다.
거리 배열을 사용하면 시작점에서 각 칸까지의 거리를 저장할 수 있습니다.
int[][] distance = new int[n][m];방문하지 않은 칸을 -1로 표시하려면 다음처럼 초기화할 수 있습니다.
for (int i = 0; i < n; i++) {
Arrays.fill(distance[i], -1);
}다음 칸으로 이동할 때는 현재 거리보다 1 큰 값을 저장합니다.
distance[nx][ny] = distance[x][y] + 1격자에서 최소 이동 횟수를 구할 때는 BFS와 distance 배열을 함께 사용합니다.
12. 격자 최단 거리 BFS 코드
격자에서 최단 거리를 구하는 기본 코드는 다음과 같습니다.
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
static int[][] distance;
public static void bfsDistance(int startX, int startY) {
Queue<int[]> queue = new LinkedList<>();
for (int i = 0; i < n; i++) {
Arrays.fill(distance[i], -1);
}
queue.offer(new int[] {startX, startY});
distance[startX][startY] = 0;
while (!queue.isEmpty()) {
int[] current = queue.poll();
int x = current[0];
int y = current[1];
for (int dir = 0; dir < 4; dir++) {
int nx = x + dx[dir];
int ny = y + dy[dir];
if (nx < 0 || ny < 0 || nx >= n || ny >= m) {
continue;
}
if (distance[nx][ny] != -1) {
continue;
}
if (map[nx][ny] == 0) {
continue;
}
distance[nx][ny] = distance[x][y] + 1;
queue.offer(new int[] {nx, ny});
}
}
}distance가 -1이 아니라면 이미 방문한 칸입니다. 따라서 distance 배열은 방문 배열 역할도 함께 할 수 있습니다.
13. 대각선 이동
문제에 따라 상하좌우뿐 아니라 대각선까지 이동할 수 있는 경우도 있습니다. 이때는 방향 배열을 8개로 만들면 됩니다.
int[] dx = {-1, -1, -1, 0, 0, 1, 1, 1};
int[] dy = {-1, 0, 1, -1, 1, -1, 0, 1};8방향 이동은 위, 아래, 왼쪽, 오른쪽뿐 아니라 네 개의 대각선 방향도 포함합니다.
| 이동 방식 | 방향 개수 |
|---|---|
| 상하좌우 | 4방향 |
| 상하좌우 + 대각선 | 8방향 |
문제에서 “대각선도 연결된 것으로 본다”라는 조건이 있다면 8방향 탐색을 사용해야 합니다.
격자 문제에서는 이동 가능한 방향 조건을 반드시 먼저 확인해야 합니다.
14. 격자 탐색의 시간복잡도
격자 탐색은 각 칸을 보통 한 번씩 방문합니다. 격자의 행이 N개, 열이 M개라면 전체 칸의 수는 N × M입니다.
| 구분 | 시간복잡도 |
|---|---|
| 2차원 DFS | O(N × M) |
| 2차원 BFS | O(N × M) |
각 칸에서 상하좌우 4방향을 확인하더라도 방향 개수는 고정되어 있습니다. 따라서 전체 시간복잡도는 O(N × M)으로 봅니다.
격자 탐색은 방문 체크를 제대로 하면 각 칸을 한 번씩만 처리합니다.
15. 격자 탐색에서 자주 하는 실수
격자 탐색 문제에서는 아래 실수를 자주 하게 됩니다.
- 행과 열을 반대로 사용하는 경우
- x와 y의 의미를 코드 중간에 바꾸는 경우
- 배열 범위 체크를 하지 않는 경우
- 범위 체크 전에 map[nx][ny]나 visited[nx][ny]를 접근하는 경우
- 방문 처리를 너무 늦게 하는 경우
- BFS에서 큐에 넣는 순간 방문 처리하지 않는 경우
- 상하좌우 문제인데 대각선까지 탐색하는 경우
- 대각선도 가능한 문제인데 4방향만 탐색하는 경우
- 최단 거리 문제에서 DFS를 사용하는 경우
특히 행과 열을 헷갈리지 않는 것이 중요합니다. 보통 map[x][y]에서 x는 행, y는 열로 정해두고 끝까지 같은 기준을 유지하는 것이 좋습니다.
x → 행
y → 열격자 탐색은 방향 배열, 범위 체크, 방문 처리 세 가지가 핵심입니다.
16. 정리
이번 글에서는 격자 탐색에 대해 정리했습니다.
- 격자 탐색은 2차원 배열에서 칸과 칸 사이를 이동하며 탐색하는 방식이다.
- 2차원 배열의 위치는 행과 열로 표현한다.
- 상하좌우 이동에는 dx, dy 방향 배열을 사용한다.
- 다음 위치를 확인할 때는 범위 체크를 가장 먼저 해야 한다.
- DFS는 연결된 영역을 깊게 탐색할 때 사용할 수 있다.
- BFS는 격자에서 최단 거리를 구할 때 자주 사용된다.
- 영역 개수는 방문하지 않은 시작점을 발견할 때마다 탐색을 시작해 구할 수 있다.
- 대각선 이동이 가능한 문제라면 8방향 탐색을 사용해야 한다.
- 격자 탐색의 시간복잡도는 보통 O(N × M)이다.
격자 탐색은 DFS와 BFS를 2차원 배열에 적용하는 대표적인 유형입니다. 처음에는 x, y와 dx, dy가 헷갈릴 수 있지만, 방향 배열과 범위 체크 순서만 익숙해지면 다양한 지도 탐색 문제를 풀 수 있습니다.
격자 탐색의 핵심은 현재 위치에서 이동 가능한 방향을 확인하고, 범위와 방문 여부를 체크한 뒤 다음 칸으로 이동하는 것입니다.
다음 글 예고
다음 글에서는 최단 거리 기초에 대해 알아보겠습니다.
BFS로 최단 거리를 구할 수 있는 조건, distance 배열 사용법, 간선 가중치가 있을 때와 없을 때의 차이를 예제로 정리해보겠습니다.
'Problem Solving > Algorithm' 카테고리의 다른 글
| [알고리즘] 33. 정렬 알고리즘 개념 (0) | 2026.07.16 |
|---|---|
| [알고리즘] 32. 최단 거리 기초 (1) | 2026.07.15 |
| [알고리즘] 30. 방문 배열 (0) | 2026.07.13 |
| [알고리즘] 29. BFS 너비 우선 탐색 (0) | 2026.07.12 |
| [알고리즘] 28. DFS 깊이 우선 탐색 (1) | 2026.07.11 |