[Java] DFS, BFS

Java로 DFS, BFS 정리하기

이 글에서는 기본적인 DFS, BFS 알고리즘에 대한 설명을 포함하지 않습니다.

Java로 각 알고리즘을 구현하는 방식에 대해 작성하였습니다.

1. 그래프를 matrix로 표현하기

public class UndirectedGraph{
	private int count; // 노드 개수
	private int [][] vertexMatrix;
	
	public UndirectedGraph(int count) {
		this.count = count;
		vertexMatrix = new int[count][count];
	}
	
	public void addEdges(int from, int to, int weight) {
		vertexMatrix[from][to] = weight;
		vertexMatrix[to][from] = weight;
	}
	
	public int[][] getMatrix(){
		return vertexMatrix;
	}
}

2. 스택을 활용한 DFS 구현

Java에서 Stack 사용법

import java.util.Stack;

public class DfsSearch {
	int count;
	boolean[] visited;
	Stack<Integer> stack;
	int[][] matrix;
	
	public DfsSearch(int count) {
		this.count = count;
		visited = new boolean[count];
		stack = new Stack<Integer>();
	}
	
	public void dfsTraversal() {
		stack.push(0);
		visited[0] = true;
		
		while(stack.isEmpty() == false) {
			int node = stack.pop();
			
			System.out.print(node + " ");
			
			for (int j = 0; j<count; j++) {
				if(matrix[node][j] != 0 && !visited[j]) {
					stack.push(j);
					visited[j] = true;
				}
			}
		}
	}
	
	public static void main(String[] args) {
		int count = 0;
		UndirectedGraph graph = new UndirectedGraph(count);
		DfsSearch dfsSearch = new DfsSearch(count);
		
		graph.addEdges(0,1,1);
		
		dfsSearch.matrix = graph.getMatrix();
		dfsSearch.dfsTraversal();
	}
}

3. DFS로 2차원 배열 영역 개수 및 크기 구하기

DFS(깊이 우선 탐색, Depth First Search)는 그래프나 2차원 배열에서 연결된 노드를 탐색할 때 자주 사용되는 알고리즘입니다.

이 예제는 2차원 배열에서 1로 연결된 영역을 DFS로 탐색하여, 전체 영역의 개수와 각 영역의 크기를 구하는 문제입니다.

map = new int[][] {
    {1, 1, 0, 0, 0},
    {1, 1, 0, 1, 1},
    {0, 0, 0, 1, 1},
    {0, 1, 1, 0, 0}
};

여기서 1은 영역의 일부, 0은 빈 공간을 의미합니다. 인접한 1들(상, 하, 좌, 우로 연결된 것들)은 하나의 영역으로 간주됩니다. 이 배열에서 총 몇 개의 영역이 있는지, 각 영역의 크기는 얼마나 되는지를 구하고자 합니다.

DFS 탐색 원리

• 방문 여부를 기록하는 visited 배열을 사용해 중복 방문을 방지합니다.
• 상하좌우로 이동 가능한 방향 벡터를 정의합니다.
• dfs(x, y) 함수는 현재 위치에서 상하좌우를 탐색하며 연결된 모든 1을 방문 처리합니다.
• main() 함수에서는 전체 배열을 순회하며 방문하지 않은 1을 만나면 새 영역의 시작으로 보고 DFS를 실행합니다.

import java.util.*;

public class Main {
    static int[][] map;
    static boolean[][] visited;
    static int n, m;
    static int areaSize;

    // 방향벡터: 상하좌우
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    public static void main(String[] args) {
        map = new int[][] {
            {1, 1, 0, 0, 0},
            {1, 1, 0, 1, 1},
            {0, 0, 0, 1, 1},
            {0, 1, 1, 0, 0}
        };

        n = map.length;
        m = map[0].length;
        visited = new boolean[n][m];

        int regionCount = 0;
        List<Integer> areaSizes = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!visited[i][j] && map[i][j] == 1) {
                    areaSize = 0;
                    dfs(i, j);
                    regionCount++;
                    areaSizes.add(areaSize);
                }
            }
        }

        System.out.println("영역 개수: " + regionCount);
        System.out.println("각 영역 크기: " + areaSizes);
    }

    public static void dfs(int x, int y) {
        visited[x][y] = true;
        areaSize++;

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx >= 0 && ny >= 0 && nx < n && ny < m) {
                if (!visited[nx][ny] && map[nx][ny] == 1) {
                    dfs(nx, ny);
                }
            }
        }
    }
}