Java/알고리즘

[알고리즘/DFS, BFS] 깊이 우선 탐색, 넓이 우선 탐색 (스택, 재귀함수, 큐, 방문 여부 배열, 그래프 연결 정보 저장 2차원 리스트)

Se On 2025. 1. 20. 14:59

🖥️ 들어가며

📌DFS
: Depth First Search, 깊이 우선 탐색
📌BFS
: Breadth First Search, 넓이 우선 탐색

 

✏️ 스택 구현 예제

  • Stack<Integer> s = new Stack<>();
  • 삽입: push()
    삭제: pop()
    최상단 원소부터 출력: peek()
import java.util.*;

public class Main {
	public static void main(String[] args) {
    	Stack<Integer> s = new Stack<>();
        
        // 삽입: push, 삭제: pop
        s.push(5);
        s.push(2);
        s.push(3);
        s.push(7);
        s.pop();
        s.push(1);
        s.push(4);
        s.pop();
        
        // 최상단 원소부터 출력: peek()
        while (!s.isEmpty()) {
        	System.out.println(s.peek() + " ");
            s.pop();
        }
    }
}

 

✏️ 큐 구현 예제

  • Queue<Integer> q = new LinkedList<>();
    큐 중에서도 연결리스트 방식으로 구현된 큐를 사용합니다.
  • 삽입: offer()
    삭제: poll()*
    *poll() 메서드: 원소를 꺼내고 반환해 줌
import java.util.*;

public class Main {
	public static void main(String[] args) {
    	Queue<Integer> q = new LinkedList<>();
        
        // 삽입: offer, 삭제: poll
        q.offer(5);
        q.offer(2);
        q.offer(3);
        q.offer(7);
        q.poll();
        q.offer(1);
        q.offer(4);
        q.poll();
        
        // 먼저 들어온 원소부터 추출
        while (!q.isEmpty()) {
        	System.out.println(q.poll() + " ");
        }
    }
}

 

✏️ 재귀함수

  • 일반적인 코딩테스트에서 재귀함수를 사용할 때는 종료조건을 반드시 명시해야 합니다. (의도적으로 무한 루프를 원하는 게 아니라면)
  • 종료조건을 제대로 명시하지 않으면 함수가 무한히 호출될 수 있습니다.
  • 모든 재귀함수는 반복문을 이용하여 동일한 기능을 구현할 수 있습니다.
  • 팩토리얼 구현
  • 최대공약수 계산(유클리드 호제법)

 

👉🏻 유클리드 호제법

  • 두 개의 자연수에 대한 최대공약수를 구하는 알고리즘입니다.
    • 두 자연수 A, B에 대하여 (A > B) A를 B로 나눈 나머지 = R
    • 이때 A와 B의 최대공약수는 B와 R의 최대공약수와 같습니다.
  • 유클리드 호제법의 아이디어를 그대로 재귀 함수로 작성할 수 있습니다.
  •  

 

 

 

 

✏️ DFS, BFS 구현 방법

1. DFS

  • 동작 과정
    1. 탐색 시작 노드를 스택에 삽입하고 방문 처리합니다.
    2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리합니다.
    방문하지 않은 노드가 없으면 스택에서 최상단 노드를 꺼냅니다.
    *방문기준: 문제 내용에 따라 상이
    3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복합니다. 
  • 응용
    • 경로 찾기
    • 위상 정렬
    • 연결 요소 찾기
    • 사이클 탐지

 

📌DFS code

  • 전역 변수
    • visited: 각 노드의 방문 여부를 저장하는 배열입니다.
      • boolean[] visited = new boolean[9]: 크기가 9인 이유는 노드가 1~8까지 있기 때문입니다.
        (0번 인덱스는 사용하지 않음)
    • graph: 그래프의 연결 관계를 저장하는 2차원 ArrayList입니다. 각 노드에 연결된 노드들의 리스트를 저장합니다.
      • ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>(); : ArrayList를 2차원 형태로 중첩해서 사용합니다.
  • dfs 함수
    • 재귀적으로 dfs를 수행합니다.
      1. 현재 노드 x를 방문 처리합니다.
      2. 현재 노드를 출력합니다.
      3. 현재 노드와 연결된 모든 노드에 대해 아직 방문하지 않은 노드라면 해당 노드로 dfs를 재귀적으로 호출합니다.
    • for (int i = 0; i < graph.get(x).size(); i++): graph.get(x)는 x 노드에 연결된 다른 노드들의 리스트입니다. 이 리스트의 크기만큼 반복문을 돌며 연결된 노드를 탐색합니다.
    • int y = graph.get(x).get(i): x 노드와 연결된 i번째 노드를 가져옵니다.
    • if (!visited[y]) dfs(y): y 노드가 아직 방문되지 않았다면 dfs(y)를 호출하여 그 노드를 재귀적으로 탐색합니다.
  • main 함수
    • graph.add(new ArrayList<Integer>(): 그래프를 나타내는 graph 리스트에 9개의 빈 ArrayList<Integer> 객체를 추가합니다. 이 리스트는 각 노드에 연결된 다른 노드들의 목록을 저장하는데 사용됩니다.
    • graph.get(1).add(2): 노드 1에 연결된 노드 2를 그래프에 추가합니다.
    • dfs(1): 깊이 우선 탐색을 시작합니다. (1번 노드에서부터 탐색 시작)
import java.util.*;

public class Main {

    public static boolean[] visited = new boolean[9];
    public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();

    // DFS 함수 정의
    public static void dfs(int x) {
        // 현재 노드를 방문 처리
        visited[x] = true;
        System.out.print(x + " ");
        // 현재 노드와 연결된 다른 노드를 재귀적으로 방문
        for (int i = 0; i < graph.get(x).size(); i++) {
            int y = graph.get(x).get(i);
            if (!visited[y]) dfs(y);
        }
    }

    public static void main(String[] args) {
        // 그래프 초기화
        for (int i = 0; i < 9; i++) {
            graph.add(new ArrayList<Integer>());
        }

        // 노드 1에 연결된 노드 정보 저장 
        graph.get(1).add(2);
        graph.get(1).add(3);
        graph.get(1).add(8);
        
        // 노드 2에 연결된 노드 정보 저장 
        graph.get(2).add(1);
        graph.get(2).add(7);
        
        // 노드 3에 연결된 노드 정보 저장 
        graph.get(3).add(1);
        graph.get(3).add(4);
        graph.get(3).add(5);
        
        // 노드 4에 연결된 노드 정보 저장 
        graph.get(4).add(3);
        graph.get(4).add(5);
        
        // 노드 5에 연결된 노드 정보 저장 
        graph.get(5).add(3);
        graph.get(5).add(4);
        
        // 노드 6에 연결된 노드 정보 저장 
        graph.get(6).add(7);
        
        // 노드 7에 연결된 노드 정보 저장 
        graph.get(7).add(2);
        graph.get(7).add(6);
        graph.get(7).add(8);
        
        // 노드 8에 연결된 노드 정보 저장 
        graph.get(8).add(1);
        graph.get(8).add(7);

        dfs(1);
    }

}

 

2. BFS

  • BFS: Queue
  • 특징
    • 시작 노드에서 가까운 노드부터 탐색합니다.
    • 큐 자료구조를 사용하여 구현합니다.
    • 최단 경로를 찾는 데 유용합니다.
    • 레벨 순서로 노드를 탐색합니다.
  • 동작 과정
    1. 시작 노드를 큐에 삽입하고 방문 처리합니다.
    2. 큐에서 노드를 꺼낸 뒤 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리합니다.
    3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복합니다.
  • 응용
    • 최단 경로 찾기
    • 네트워크 탐색
    • 웹 크롤링
    • 미로 찾기
    • 그래프의 연결 요소 찾기

 

📌BFS code

  • get(): ArrayList에서 특정 값을 가져올 때 사용합니다.
  • 전역 변수
    • visited: 각 노드의 방문 여부를 저장하는 배열입니다.
      • boolean[] visited = new boolean[9]: 크기가 9인 이유는 노드가 1~8까지 있기 때문입니다.
        (0번 인덱스는 사용하지 않음)
    • graph: 그래프의 연결 관계를 저장하는 2차원 ArrayList입니다. 각 노드에 연결된 노드들의 리스트를 저장합니다.
      • ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>(); : ArrayList를 2차원 형태로 중첩해서 사용합니다.
  • bfs 함수
    • Queue<Integer> q = new LinkedList<>(): 큐를 사용하여 노드를 탐색합니다.
    • q.offer(start): 탐색을 시작할 노드 start를 큐에 추가합니다.
    • visited[start] = true: 현재 노드를 방문 처리합니다.
    • while(!q.isEmpty()) {...}: 큐가 비어있지 않은 동안 반복문을 실행합니다.
      • int x = q.poll(): 큐에서 원소를 하나 꺼냅니다.
      • for (int i = 0; i < graph.get(x).size(); i++) {...}: x 노드와 연결된 다른 노드들의 리스트를 순회하면서 x와 연결된 노드를 탐색합니다.
        • int y = graph.get(x).get(i): x 노드와 연결된 i번째 노드를 y 변수에 저장합니다.
        • if (!visited[y]) {...}: y 노드가 아직 방문되지 않았다면, y 노드를 큐에 추가하고 방문 처리합니다.
  • main 함수
    • graph.add(new ArrayList<Integer>(): 그래프를 나타내는 graph 리스트에 9개의 빈 ArrayList<Integer> 객체를 추가합니다. 이 리스트는 각 노드에 연결된 다른 노드들의 목록을 저장하는데 사용됩니다.
    • graph.get(1).add(2): 노드 1에 연결된 노드 2를 그래프에 추가합니다.
    • bfs(1): 넓이 우선 탐색을 시작합니다. (1번 노드에서부터 탐색 시작)

 

 

import java.util.*;

public class Main {

    public static boolean[] visited = new boolean[9];
    public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();

    // BFS 함수 정의
    public static void bfs(int start) {
        Queue<Integer> q = new LinkedList<>();
        q.offer(start);
        // 현재 노드를 방문 처리
        visited[start] = true;
        // 큐가 빌 때까지 반복
        while(!q.isEmpty()) {
            // 큐에서 하나의 원소를 뽑아 출력
            int x = q.poll();
            System.out.print(x + " ");
            // 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
            for(int i = 0; i < graph.get(x).size(); i++) {
                int y = graph.get(x).get(i);
                if(!visited[y]) {
                    q.offer(y);
                    visited[y] = true;
                }
            }
        }
    }

    public static void main(String[] args) {
        // 그래프 초기화
        for (int i = 0; i < 9; i++) {
            graph.add(new ArrayList<Integer>());
        }

        // 노드 1에 연결된 노드 정보 저장 
        graph.get(1).add(2);
        graph.get(1).add(3);
        graph.get(1).add(8);
        
        // 노드 2에 연결된 노드 정보 저장 
        graph.get(2).add(1);
        graph.get(2).add(7);
        
        // 노드 3에 연결된 노드 정보 저장 
        graph.get(3).add(1);
        graph.get(3).add(4);
        graph.get(3).add(5);
        
        // 노드 4에 연결된 노드 정보 저장 
        graph.get(4).add(3);
        graph.get(4).add(5);
        
        // 노드 5에 연결된 노드 정보 저장 
        graph.get(5).add(3);
        graph.get(5).add(4);
        
        // 노드 6에 연결된 노드 정보 저장 
        graph.get(6).add(7);
        
        // 노드 7에 연결된 노드 정보 저장 
        graph.get(7).add(2);
        graph.get(7).add(6);
        graph.get(7).add(8);
        
        // 노드 8에 연결된 노드 정보 저장 
        graph.get(8).add(1);
        graph.get(8).add(7);

        bfs(1);
    }

}

 

 

 

📒 정리하면

  1. DFS: 깊이 우선 탐색, 스택 또는 재귀를 사용합니다. 경로 탐색, 위상 정렬 등에 사용됩니다.
    (방문 여부 배열, 그래프 연결 정보 2차원 리스트, 시작노드 → 인접노드를 재귀적으로 탐색합니다.)
  2. BFS: 넓이 우선 탐색, 큐를 사용합니다. 최단 경로 찾기에 유용합니다.
    (방문 여부 배열, 그래프 연결 정보 2차원 리스트, 시작노드 → 인접노드를 큐에서 순차적으로 방문합니다.)
  3. 스택(Stack): 삽입 push(), 삭제 pop(), 최상위 요소 확인 peek()
    큐(Queue): 삽입 offer(), 삭제 poll() - 값을 반환하면서 삭제합니다.
  4. 재귀함수: (무한루프를 원하는 게 아니라면) 종료 조건을 명시해야 하며, 반복문으로 대체할 수 있습니다.
    (ex: 팩토리얼 계산, 유클리드 호제법(최대공약수 계산))
  5. ⭐⭐⭐ 방문 여부 배열(0번 인덱스는 사용하지 않으므로 +1 사이즈로),
    ⭐⭐⭐ 그래프 연결 정보 저장 2차원 리스트(ArrayList<ArrayList<Integer>> graph)
반응형