[알고리즘] 30. 방문 배열
지난 글에서는 BFS 너비 우선 탐색에 대해 정리했습니다. 이번 글에서는 DFS와 BFS에서 빠지지 않고 등장하는 방문 배열에 대해 알아보겠습니다.
방문 배열은 어떤 정점이나 칸을 이미 확인했는지 기록하는 배열입니다. 그래프나 2차원 배열을 탐색할 때 방문 배열을 제대로 사용하지 않으면 같은 위치를 반복해서 방문하거나, 무한 반복처럼 동작할 수 있습니다.
방문 배열은 이미 방문한 정점이나 위치를 다시 방문하지 않기 위해 사용하는 체크 배열입니다.
1. 방문 배열이란?
방문 배열은 이름 그대로 방문 여부를 저장하는 배열입니다. 어떤 정점이나 위치를 한 번 방문했다면 true로 표시하고, 아직 방문하지 않았다면 false 상태로 둡니다.
visited[1] = true → 1번 정점 방문 완료
visited[2] = false → 2번 정점 아직 방문하지 않음예를 들어 정점이 1번부터 5번까지 있다면 다음처럼 방문 배열을 만들 수 있습니다.
boolean[] visited = new boolean[6];정점 번호가 1부터 시작하는 문제에서는 보통 배열 크기를 n + 1로 만듭니다. 그래야 visited[1]부터 visited[n]까지 자연스럽게 사용할 수 있습니다.
방문 배열은 이미 처리한 대상을 다시 처리하지 않기 위한 표시입니다.
2. 방문 배열이 필요한 이유
그래프에는 사이클이 있을 수 있습니다. 사이클은 어떤 정점에서 출발해 다시 자기 자신으로 돌아올 수 있는 구조입니다.
1 --- 2
| |
3 --- 4위 그래프에서 1번에서 출발해 2번, 4번, 3번으로 이동하면 다시 1번으로 돌아올 수 있습니다. 방문 체크를 하지 않으면 이미 방문한 정점을 계속 다시 방문하게 됩니다.
1 → 2 → 4 → 3 → 1 → 2 → 4 → 3 → ...이런 반복을 막기 위해 방문 배열이 필요합니다. 한 번 방문한 정점은 다시 방문하지 않도록 막아주는 역할을 합니다.
3. boolean 방문 배열
가장 기본적인 방문 배열은 boolean 타입으로 만듭니다. boolean 배열의 기본값은 false입니다.
int n = 5;
boolean[] visited = new boolean[n + 1];
System.out.println(visited[1]);출력 결과는 다음과 같습니다.
false아직 아무 정점도 방문하지 않았으므로 false입니다. 방문한 정점은 true로 바꿉니다.
visited[1] = true;이렇게 하면 1번 정점을 방문했다는 의미가 됩니다.
boolean 방문 배열에서는 false가 미방문, true가 방문을 의미합니다.
4. DFS에서 방문 배열 사용하기
DFS에서는 현재 정점에 들어오자마자 방문 처리를 하는 경우가 많습니다. 그래야 같은 정점으로 다시 들어오는 일을 막을 수 있습니다.
static ArrayList<Integer>[] graph;
static boolean[] visited;
public static void dfs(int current) {
visited[current] = true;
for (int next : graph[current]) {
if (!visited[next]) {
dfs(next);
}
}
}DFS 흐름은 다음과 같습니다.
- 현재 정점을 방문 처리한다.
- 현재 정점과 연결된 정점을 확인한다.
- 아직 방문하지 않은 정점이면 DFS를 호출한다.
- 이미 방문한 정점이면 건너뛴다.
DFS에서는 함수에 들어오자마자 방문 처리하는 방식이 안전합니다.
5. BFS에서 방문 배열 사용하기
BFS에서는 보통 정점을 큐에 넣는 순간 방문 처리합니다. 큐에 넣은 뒤 방문 처리를 미루면 같은 정점이 여러 번 큐에 들어갈 수 있기 때문입니다.
public static void bfs(int start) {
Queue<Integer> queue = new LinkedList<>();
queue.offer(start);
visited[start] = true;
while (!queue.isEmpty()) {
int current = queue.poll();
for (int next : graph[current]) {
if (!visited[next]) {
visited[next] = true;
queue.offer(next);
}
}
}
}BFS에서는 아래 순서를 기억하면 좋습니다.
큐에 넣기
→ 방문 처리
→ 나중에 큐에서 꺼내 처리방문 처리를 큐에서 꺼낼 때 하면 같은 정점이 여러 경로를 통해 중복으로 큐에 들어갈 수 있습니다. 그래서 BFS에서는 큐에 넣을 때 방문 처리하는 방식이 안전합니다.
BFS에서는 큐에 넣는 순간 방문 처리해야 중복 삽입을 막을 수 있습니다.
6. 방문 처리 시점 비교
DFS와 BFS 모두 방문 배열을 사용하지만, 방문 처리 시점을 이해하는 것이 중요합니다.
| 탐색 | 방문 처리 시점 | 이유 |
|---|---|---|
| DFS | 현재 정점에 들어왔을 때 | 재귀로 같은 정점에 다시 들어오는 것을 방지 |
| BFS | 큐에 넣는 순간 | 같은 정점이 큐에 중복으로 들어가는 것을 방지 |
둘 다 핵심은 같습니다. 이미 처리하기로 결정한 대상은 다시 처리하지 않도록 표시하는 것입니다.
7. 방문 배열이 없으면 생기는 문제
방문 배열이 없으면 그래프 탐색에서 같은 정점을 계속 반복해서 방문할 수 있습니다.
1 --- 2
| |
3 --- 41번에서 2번으로 이동하고, 2번에서 다시 1번으로 이동할 수 있습니다. 이미 방문한 정점인지 확인하지 않으면 탐색이 끝나지 않을 수 있습니다.
특히 무방향 그래프에서는 간선을 양쪽으로 저장하기 때문에 방문 배열이 더욱 중요합니다.
graph[a].add(b);
graph[b].add(a);a에서 b로 갈 수 있고, b에서 다시 a로 갈 수 있기 때문에 방문 체크를 하지 않으면 되돌아가는 탐색이 반복될 수 있습니다.
8. 2차원 배열에서 방문 배열
그래프가 아니라 2차원 배열에서도 방문 배열을 자주 사용합니다. 미로, 지도, 섬의 개수, 영역 탐색 문제에서 많이 등장합니다.
1 1 0
0 1 0
1 0 12차원 배열에서는 위치가 행과 열로 표현됩니다. 따라서 방문 배열도 2차원으로 만듭니다.
boolean[][] visited = new boolean[n][m];visited[x][y]가 true라면 x행 y열 위치를 이미 방문했다는 의미입니다.
visited[0][0] = true → 0행 0열 방문 완료
visited[1][2] = false → 1행 2열 아직 미방문2차원 탐색에서는 visited[x][y]로 위치 방문 여부를 관리합니다.
9. 2차원 DFS에서 visited 사용하기
2차원 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);
}
}2차원 탐색에서는 보통 아래 순서로 확인합니다.
- 배열 범위를 벗어났는지 확인한다.
- 이미 방문했는지 확인한다.
- 이동 가능한 칸인지 확인한다.
- 조건을 만족하면 방문한다.
2차원 탐색에서는 범위 체크를 방문 배열 접근보다 먼저 해야 안전합니다.
10. 2차원 BFS에서 visited 사용하기
2차원 BFS에서는 시작 위치를 큐에 넣고 방문 처리합니다. 그다음 큐에서 위치를 꺼내며 상하좌우를 확인합니다.
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에서도 큐에 넣는 순간 visited[nx][ny]를 true로 바꾸는 것이 안전합니다. 같은 칸이 여러 번 큐에 들어가는 일을 막을 수 있습니다.
11. visited와 distance 배열의 차이
BFS 최단 거리 문제에서는 visited 배열 대신 distance 배열을 사용하기도 합니다. distance 배열은 방문 여부와 거리 정보를 동시에 담을 수 있습니다.
| 배열 | 역할 |
|---|---|
| visited | 방문했는지 여부만 저장 |
| distance | 시작점부터의 거리 저장 |
distance 배열을 -1로 초기화하면 -1은 아직 방문하지 않았다는 뜻으로 사용할 수 있습니다.
int[] distance = new int[n + 1];
Arrays.fill(distance, -1);
distance[start] = 0;이후 아직 방문하지 않은 정점인지 확인할 때는 distance[next] == -1을 사용할 수 있습니다.
if (distance[next] == -1) {
distance[next] = distance[current] + 1;
queue.offer(next);
}최단 거리 문제에서는 visited 대신 distance 배열을 방문 체크로 활용할 수 있습니다.
12. 방문 배열 초기화
하나의 탐색이 끝난 뒤 다시 새로운 탐색을 해야 한다면 방문 배열을 초기화해야 할 수 있습니다.
Arrays.fill(visited, false);1차원 boolean 배열은 Arrays.fill()로 초기화할 수 있습니다.
2차원 boolean 배열은 행마다 초기화할 수 있습니다.
for (int i = 0; i < n; i++) {
Arrays.fill(visited[i], false);
}하지만 연결 요소 개수처럼 전체 그래프를 한 번 훑는 문제에서는 탐색이 끝날 때마다 visited를 초기화하면 안 됩니다. 이미 방문한 영역을 기억해야 하기 때문입니다.
방문 배열 초기화는 문제의 목적에 따라 해야 할 때도 있고, 하면 안 될 때도 있습니다.
13. 연결 요소 개수와 방문 배열
연결 요소 개수를 세는 문제에서는 방문 배열을 전체 탐색 동안 유지해야 합니다.
1 --- 2 3 --- 4 5위 그래프에는 연결 요소가 3개 있습니다. 모든 정점을 확인하면서 아직 방문하지 않은 정점에서 DFS나 BFS를 시작합니다.
int count = 0;
for (int i = 1; i <= n; i++) {
if (!visited[i]) {
dfs(i);
count++;
}
}
System.out.println(count);새로운 DFS가 시작될 때마다 새로운 연결 요소를 발견한 것입니다. 이때 visited를 초기화하면 이미 방문한 정점을 다시 세게 되므로 잘못된 결과가 나올 수 있습니다.
14. 방문 배열 없이 가능한 경우
모든 탐색 문제에서 반드시 별도의 visited 배열이 필요한 것은 아닙니다. 문제에 따라 원본 배열 값을 바꿔 방문 처리하는 경우도 있습니다.
예를 들어 2차원 지도에서 1은 땅, 0은 바다라고 할 때, 방문한 땅을 0으로 바꿔버릴 수 있습니다.
map[x][y] = 0;이렇게 하면 따로 visited 배열을 만들지 않아도 다시 방문하지 않게 됩니다. 하지만 원본 데이터가 이후에도 필요하다면 이 방식은 위험할 수 있습니다.
| 방식 | 장점 | 주의할 점 |
|---|---|---|
| visited 배열 사용 | 원본 데이터 유지 | 메모리 추가 사용 |
| 원본 값 변경 | 별도 배열 불필요 | 원본 데이터가 바뀜 |
원본 배열을 바꿔도 되는 문제인지 확인한 뒤 방문 처리를 선택해야 합니다.
15. 방문 배열에서 자주 하는 실수
방문 배열을 사용할 때는 아래 실수를 조심해야 합니다.
- 방문 배열을 만들지 않아 같은 정점을 반복 방문하는 경우
- 방문 처리를 너무 늦게 해서 중복 탐색이 발생하는 경우
- BFS에서 큐에 넣을 때 방문 처리하지 않는 경우
- 2차원 배열에서 범위 체크 전에 visited[nx][ny]를 확인하는 경우
- 정점 번호가 1부터 시작하는데 visited 크기를 n으로만 만드는 경우
- 연결 요소 문제에서 탐색할 때마다 visited를 초기화하는 경우
- 원본 배열을 바꾸면 안 되는 문제에서 값을 직접 바꾸는 경우
특히 2차원 배열에서는 아래 순서가 중요합니다.
1. 범위 체크
2. 방문 체크
3. 이동 가능 여부 체크
4. 방문 처리방문 배열 실수는 대부분 방문 처리 시점과 범위 체크 순서에서 발생합니다.
16. 정리
이번 글에서는 방문 배열에 대해 정리했습니다.
- 방문 배열은 이미 방문한 정점이나 위치를 표시하는 배열이다.
- boolean 배열에서는 false가 미방문, true가 방문을 의미한다.
- 그래프에 사이클이 있을 수 있으므로 방문 배열이 필요하다.
- DFS에서는 현재 정점에 들어왔을 때 방문 처리하는 경우가 많다.
- BFS에서는 큐에 넣는 순간 방문 처리하는 것이 안전하다.
- 2차원 배열에서는 visited[x][y] 형태로 방문 여부를 관리한다.
- 최단 거리 BFS에서는 distance 배열이 방문 체크 역할을 할 수 있다.
- 문제에 따라 원본 배열 값을 바꿔 방문 처리할 수도 있다.
방문 배열은 DFS와 BFS를 안정적으로 구현하기 위한 핵심 도구입니다. 단순히 true와 false를 저장하는 배열처럼 보이지만, 방문 처리 시점이 조금만 어긋나도 중복 탐색이나 무한 반복이 발생할 수 있습니다.
방문 배열의 핵심은 이미 처리한 대상을 다시 처리하지 않도록 정확한 시점에 표시하는 것입니다.
다음 글 예고
다음 글에서는 격자 탐색에 대해 알아보겠습니다.
2차원 배열에서 상하좌우로 이동하는 방법, dx와 dy 방향 배열, 범위 체크, DFS와 BFS를 이용한 지도 탐색을 예제로 정리해보겠습니다.
'Problem Solving > Algorithm' 카테고리의 다른 글
| [알고리즘] 32. 최단 거리 기초 (1) | 2026.07.15 |
|---|---|
| [알고리즘] 31. 격자 탐색 (0) | 2026.07.14 |
| [알고리즘] 29. BFS 너비 우선 탐색 (0) | 2026.07.12 |
| [알고리즘] 28. DFS 깊이 우선 탐색 (1) | 2026.07.11 |
| [알고리즘] 27. 이분 탐색 응용 (0) | 2026.07.10 |