[To Be Algorithm Genius] (1) BFS, DFS

유영재·2024년 4월 19일

BFS DFS Java algorithm 인접 리스트

To Be Algorithm Genius

목록 보기

1/3

To Be Algorithm Genius 시리즈, 지금 시작합니다.

첫번째로, 맨날 헷갈리고 어려운 (저만 그런가요?) BFS와 DFS입니다.
한번 가볼까요 ? 따라오세요 얼른. Come on.

0. 인접 리스트

인접 리스트라고 들어보셨나요? ~~못들어봤다구요? 들어봤다구요? 알겠습니다.~~
요렇게 생긴 정점과 간선으로 이루어진 그래프가 있다고 해보죠.
일반적으로 문제에서 그래프의 정보는 아래와 같이 주어집니다.

[A,B] A는 B로 이동할 수 있습니다.

[1,2] 
[2,3]
[2,4]
[5,2]
[5,1]
[5,4]

이렇게 간선의 정보가 주어지고
여기서 정점 2에서 갈 수 있는 정점은 어디가 있냐고 물어본다면?
[2, ? ] 인 데이터들을 전부 찾아야 하므로 O(N) 의 시간이 걸릴 겁니다.
이걸 조금 더 효율적으로 찾을 수 없을까? 고민했겠죠?

💡 인접 리스트
어떤 정점 V에 연결된 정점을 효율적으로 알아내는 방법입니다.
List를 정점의 개수만큼 가진 2차원 배열과 같습니다.

// 인접 리스트
List[정점 번호] = [해당 정점에서 이동 가능한 정점들]

List[1] = [2]
List[2] = [3,4]
List[3] = []
List[4] = []
List[5] = [1,2,4]

이 방법을 사용하면 아까처럼 정점 2에서 이동 가능한 정점은 어디냐고 물어봤을 때, O(1) 만에 탐색할 수 있게 됩니다 😎

근데 인접 리스트는 정점과 간선이 적게 연결되어 있는 위의 그래프 형식에서는 유용하지만, 바둑판 배열에서는 오히려 더 시간이 많이 걸릴 수 있어요!

인접 리스트를 알고있으면 분명히 도움되는 날이 올겁니다 진짜로! 🙌

1. BFS

Breadth-First Search, 너비 우선 탐색

1. BFS가 뭔데 ?

탐색의 시작점에서 가까운 정점부터 방문하는 탐색 방법
간선의 가중치가 모두 동일한 경우, 최단 거리를 구할 수 있다.
일반적으로 큐(Queue) 를 이용한다.
동일한 정점을 재방문하지 않을 경우, 다음에 방문할 정점을 큐에 넣을 때 해당 정점에 대해 방문 처리를 한다. (중요!!)
방문 처리 없이 동일한 정점을 재방문하면 시간 초과가 발생할 수 있다.

2. 구현 방법

비어있는 큐, 방문 체크용 배열, (필요하면) 최단 거리 배열을 만듭니다.
시작 정점을 큐에 넣고, 방문 체크를 해줍니다.
큐에 데이터가 남아있을 때까지 아래의 과정을 반복합니다. 🔁
1. 큐에서 정점을 꺼냅니다.
2. 해당 정점에서 방문 가능한 정점을 큐에 넣습니다. (이미 방문한 정점은 제외)
3. (필요한 경우) 해당 정점이 유효한지(이동 가능한지) 체크
4. (필요한 경우) 꺼낸 정점의 최단거리에서 +1 한 값을 다음 정점의 최단거리로 저장합니다.
5. 큐에 정점을 넣으면서 해당 정점에 대해 방문했음을 저장합니다.

3. 예시 문제

문제 링크 (프로그래머스 : 게임 맵 최단거리)

import java.util.ArrayDeque;

class Solution {
	// 상하좌우 이동을 for문 1개로 쓰기 위해서 
    public static int [] rx = {0, 0, 1, -1};
    public static int [] ry = {1, -1, 0, 0};

    private static class Node { // 정점 클래스
        int r, c;

        public Node(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }

    public int solution(int[][] maps) {
        int N = maps.length;
        int M = maps[0].length;

        ArrayDeque<Node> queue = new ArrayDeque<>();
        boolean [][] visited = new boolean[N][M]; // 방문 배열
        int [][] dist = new int [N][M]; // 최단거리 배열

        queue.addLast(new Node(0,0)); // 시작 정점을 큐에 넣고
        visited[0][0] = true; // 방문 체크
        dist[0][0] = 1; // 최단거리는 일단 1이겠죠?

        while(!queue.isEmpty()) { // 큐에 데이터가 남아있으면 계속 순회
            Node now = queue.pollFirst(); // 현재 위치의 정점을 꺼내고

            for (int i = 0; i < 4; i++) { // 상하좌우로 이동
                int nr = now.r + rx[i];
                int nc = now.c + ry[i];

                if (nr < 0 || nc < 0 || nr >= N || nc >= M) // 맵 밖으로 벗어날 때
                    continue;

                if (maps[nr][nc] == 0) // 벽일 때
                    continue;

                if (!visited[nr][nc]) { // 방문하지 않은 정점이라면
                    visited[nr][nc] = true; // 방문 체크
                    queue.addLast(new Node(nr, nc)); // 현재 정점을 큐에 넣고
                    dist[nr][nc] = dist[now.r][now.c] + 1; // 현재 정점의 최단 거리 +1 해서 이동한 정점의 최단거리로 넣어주기
                }
            }
        }
		// 도달할 수 없는 곳이라면 -1, 가능하면 마지막 정점의 최단거리를 출력
        return dist[N-1][M-1] == 0 ? -1 : dist[N-1][M-1]; 
    }
}

💡 왜 큐에 정점을 넣으면서 해당 정점에 대해 방문 체크를 해야할까 ?

방문 체크를 큐에서 꺼낼 때
즉 Node now = queue.pollFirst(); 이 부분에서 방문 체크를 하게되면,
같은 정점이 큐에 중복으로 들어가기 때문에 시간 복잡도는 늘어나고 BFS가 적절히 사용되지 않습니다.

따라서, 방문 체크는 무조건 방문 가능한 정점을 큐에 집어 넣음과 동시에 해주셔야 합니다!

2. DFS

Depth-First Search, 깊이 우선 탐색

1. DFS가 뭔데 ?

정해진 규칙에 의해 시작 정점에서 멀어지는 방향을 우선으로 탐색하는 방법
일반적으로 재귀함수로 구현
그래프가 트리 형태일 때, DFS가 자주 쓰임
최단 거리를 구하기에는 적합한 알고리즘이 아님
Backtracking과 비슷함 (재귀로 구현된다는 점에서)

2. 구현 방법

방문 체크용 배열을 만듭니다.
현재 정점을 파라미터로 넘기는 메소드를 정의합니다.
메소드 내부에서 -
1. 현재 정점이 이미 방문된 정점이면 return
2. 현재 정점 방문 체크
3. 해당 정점에서 방문 가능한 다음 정점을 파라미터로 넘기면서 현재 메소드를 재귀 호출
  (필요한 경우) 해당 정점이 유효한지(이동 가능한지) 체크

3. 예시 문제

문제 링크 (프로그래머스 : 네트워크)

class Solution {
    public static boolean [] visited;
    public static int [][] computer;
    public static int answer;
    
    public int solution(int n, int[][] computers) {
        answer = 0;
        computer = computers; // shallow copy
        visited = new boolean[n];
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                dfs(i); // 방문하지 않은 정점에 대해 dfs 돌리기
                answer++; // 리턴되면 answer+1
            }

        }

        return answer;
    }

    public static void dfs(int now) {
        for (int i = 0; i < computer[now].length; i++) {
            if (computer[now][i] == 1 && !visited[i]) { 
                visited[now] = true; // 방문처리
                dfs(i); // 이동한 정점을 넘기면서 dfs 재귀호출
            }
        }
    }
}