[TIL, 일일 회고] 2025.02.02 - 그래프 탐색(DFS, BFS)에서 방문 배열(visited)의 차원 결정하기

개요

알고리즘 문제를 풀다 보면 그래프 탐색 알고리즘(BFS, DFS) 을 사용할 때, 중복 방문을 방지하기 위해 boolean 배열을 활용하게 됩니다.

 

이때, 방문 체크용 boolean 배열을 1차원으로 사용할지, 2차원으로 사용할지 헷갈리는 경우가 많습니다.

이는 탐색 대상이 되는 그래프의 구조를 확인하면 쉽게 결정할 수 있습니다. 본 글에서는 그래프의 형태에 따라 boolean 배열을 어떻게 설정해야 하는지 정리하고자 합니다.

 

1차원 boolean 배열을 사용하는 경우

 

• 그래프가 일반적인 정점(Node) 중심의 탐색일 때
• 인접 리스트 또는 인접 행렬로 그래프가 표현된 경우
• 정점 개수가 N개라면, boolean[N] 크기의 방문 배열을 사용

 

예제: 그래프의 각 정점을 방문하는 경우

boolean[] visited = new boolean[N]; // 정점 방문 여부 저장

void dfs(int node) {
    visited[node] = true;
    for (int next : graph[node]) { // 현재 노드와 연결된 노드들 탐색
        if (!visited[next]) {
            dfs(next);
        }
    }
}

 

2차원 boolean 배열을 사용하는 경우

 

• 그래프가 좌표(Point) 중심의 탐색일 때
• 즉, 2D 격자를 탐색하는 경우
  • 예: NxM 크기의 지도, 미로, 체스판 등
• (x, y) 위치를 방문했는지를 저장하려면 boolean[N][M] 크기의 배열을 사용

예제: 미로 탐색 (BFS / DFS)

boolean[][] visited = new boolean[N][M]; // 2D 방문 배열

 

 

void bfs(int x, int y) {
    Queue<int[]> queue = new LinkedList<>();
    queue.add(new int[]{x, y});
    visited[x][y] = true;

    while (!queue.isEmpty()) {
        int[] cur = queue.poll();
        int cx = cur[0], cy = cur[1];

        for (int d = 0; d < 4; d++) { // 4방향 이동 (상하좌우)
            int nx = cx + dx[d], ny = cy + dy[d];

            if (nx >= 0 && ny >= 0 && nx < N && ny < M && !visited[nx][ny]) {
                visited[nx][ny] = true;
                queue.add(new int[]{nx, ny});
            }
        }
    }
}​

 

 

결론

• ✅ 그래프 탐색(정점 기준) → boolean[N] (1차원)
• ✅ 격자(좌표 기준) 탐색 → boolean[N][M] (2차원)
  • 즉, 탐색 대상이 "정점"이면 1차원, "좌표"이면 2차원