8. [Java] 그래프 기초 / BFS (너비 우선 탐색)

Graph

• 일반적으로 그래프에서 정점의 표현은 v (Vertex), 간선의 표현은 E (Edge)로 한다.
• 바둑판 형태의 맵에서 탐색하는 것 또한 각 칸을 정점, 다른 칸으로 이동 가능한 방법을 간선으로 볼 수 있다.
• 일반적인 문제에선 정점과 간선의 조합으로 문제가 많이 나오기 떄문에 그패의 정보를 저장할 떄 인접리스트를 많이 사용하게 되지만, 기업 입사 코딩테스트에서는 바둑판 형태의 그래프가 더 자주 나온다.

상하좌우로 이동 가능할 경우 간선은?

• 기본적으로 1칸당 4개의 간선이 있는 것으로 생각
• 범위 밖으로 나가는 경우에 대해서는 예외처리

---

인접 리스트

그래프의 정보는 코딩테스트에서 어떻게 주어지고, 어떻게 저장을 해야 탐색에 유리할까?

일반적으로 그래프의 정보는 아래와 같이 주어진다.

 

[A, B] : A에서 B로 이동 가능하다.

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

 

입력값과 동일하게 단순한 리스트로 저장하면, 어떤 정점 X에서 이동 가능한 정점을 탐색하기 위해 O(E)의 시간이 걸린다.

예를 들어, 1번 정점에서 이동 가능한 정점을 탐색하려면, 이 간선 데이터를 전부 탐색해서 [1,X] 인 데이터를 다 찾아내야 한다.

 

어떤 정점 X에서 연결된 (이동 가능한) 다음 정점을 효율적으로 알아내는 방법으로 인접리스트를 사용한다.

 

List는 정점의 개수만큼 가진 2차원 배열과 같은 형태이다.

List[정점] = [해당 정점에서 탐색 가능한 정점]

List[1] = [2]

List[2] = [3,4]

List[3] = []

List[4] = []

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

 

위와 같이 만들면 어떤 정점 X가 5일 때,

ArrayList[X]에 [1,2,4]가 담겨있기 때문에 X에서 이동 가능한 정점들을 빠르게 O(1)만에 탐색할 수 있다.

import java.util.ArrayList;

public class test {

    private static final int[][] input = {{1, 2}, {2, 3}, {2, 4}, {5, 2}, {5, 1}, {5, 4}};

    public static void main(String[] args) {
        int N = 5; // 정점의 개수
        ArrayList<Integer>[] adjList = new ArrayList[N + 1];

        for(int i = 1; i <= N; i++) {
            adjList[i] = new ArrayList<>(); // 인접리스트 초기화
        }

        for (int[] arr : input) {
            adjList[arr[0]].add(arr[1]); 
            // 예시1 :1번 정점에서 이동 가능한 곳은 2번 정점 (1 -> 2)
        }

        for(int next : adjList[5]) {
            System.out.println("next : " + next);
        }
    }
}

위의 코드는 인접 리스트에서 5번 정점에서 갈 수 있는 다음 정점을 출력하는 예시 코드이다.

ArrayList<Integer>[] adjList = new ArrayList[N + 1]; 는 N + 1 크기의 ArrayList<Integer> 타입의 배열을 생성하는 코드.

이 배열의 각 요소는 ArrayList<Integer> 객체를 가리킬 수 있으며, 이를 통해 인접 리스트와 같은 그래프 구조를 표현할 수 있다.
따라서, adjList는 ArrayList 객체를 담고 있는 1차원 배열이다.

각 ArrayList는 그래프의 각 노드에 연결된 이웃 노드들을 저장하는 데 사용될 수 있다.

 

• 굳이 ArrayList의 배열로 만드는 이유는 2차원 배열로 arr[V][V]와 같이 데이터를 저장할 경우, 정점의 개수 V가 100,000개일 경우에 메모리 초과 (공간복잡도 V^2)가 발생할 수 있기 때문이다.
  ArrayList는 동적 배열이기 때문에 공간복잡도가 O(V+E) 가 된다.
  
  
• 인접 리스트는 DFS, BFS, 다익스트라 알고리즘과 같은 그래프 문제에서 간혹 필요한 케이스가 있으니, 이렇게 할 수 있다 정도까지만 알아두자. 자주 출제되지는 않는다.

---

⭐️ BFS (Breadth First Search : 너비 우선 탐색)

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

📝 BFS (Breadth First Search) 탐색 구현 방법

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

바둑판 모양에서 BFS 탐색을 해보자.

상하좌우 4개 방향으로 이동 가능하다고 할 때,

정점 (2,2) 기준에서 보면 이동 가능한 정점은 아래와 같다.

상 (1,2)

하 (3,2)

좌 (2,1)

우 (2,3)

 

이를 정점 (2,2) 기준에서 보면 아래와 같다

상 (2 + -1, 2 + 0)

하 (2 + 1, 2 + 0)

좌 (2 + 0, 2 + -1)

우 (2 + 0, 2 + 1)

 

이를 나열하면 [-1, 1, 0, 0], [0, 0, -1, 1] 이 된다.

rx = [-1, 1, 0, 0]

ry = [0, 0, -1, 1]

라고 정의했을 때,

 

현재 위치를 (now_r, now_c) 라 가정하면, 이동가능한 다음 정점은 아래와 같다.

     for (i = 0 -> 4) : // 상하좌우 탐색
                    now_r = now_r + rx[i];
                    now_c = now_c + ry[i];

 

<BFS 예시 코드>

https://school.programmers.co.kr/learn/courses/30/lessons/1844

프로그래머스

기본 템플릿으로 외우면 좋다

import java.util.ArrayDeque;
import java.util.Arrays;

public class BFS_test {

    private static final int[] rx = {0, 0, 1, -1};
    private static final 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;
        }

    }

    // map이 아래 조건처럼 주어질 때, 최단 거리 구하기
    public static void main(String[] args) {
        int N = 5;
        int M = 5;
        int[][] map = new int[N][N];
        for (int i = 0; i < N; i++) {
            Arrays.fill(map[i], 1); // 모든 배열의 칸을 1로 초기화
        }

        ArrayDeque<Node> queue = new ArrayDeque<>(); // 비어있는 큐
        boolean[][] visited = new boolean[N][N]; // 정점에 대한 방문처리 배열
        int[][] dist = new int[N][N]; // 최단거리 배열

        queue.addLast(new Node(0, 0)); // 시작 정점을 큐에 넣고,
        visited[0][0] = true; // 방문 배열에 방문했음을 저장
        
        // 문제 조건에 맞춰, 이 조건 추가
        dist[0][0] = 1; // 없으면, 0

        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 >= N) {
                    continue; // map 밖으로 나가는 경우, 예외처리
                }

                if (map[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
                }
            }
        }

        for (int i = 0; i < N; i++) {
            System.out.println(Arrays.toString(dist[i]));
        }
        System.out.println(dist[N - 1][N - 1]);
    }

}

결과화면