[탐색] 너비 우선 탐색(BFS)

💡 먼저 부족하지만 저의 글을 읽어주셔서 감사드립니다!!!
참고 정도로 해주셨으면 좋겠습니다.
해당 강의는 여기 사이트 입니다.

 

너비 우선 탐색(Breadth First Search)

• 시작 노드에서 인접 노드를 모두 방문하고, 방문한 노드에서 인접 노드를 모두 방문하는 것을 반복
• 그래프 순회 방법 중 하나
• 간선에 가중치를 줄 수 있다?

 

 

👉 큐(Queue)

• 보통 Queue는 LinkedList 로 만든다.

public class App {
	
    static final int MAX_N = 10; // 문제에 따라서 최대 노드 개수를 정해줘야 한다.  // 어떤 기준으로 정할까?
    static int vertex, line;
    static int[][] Graph = new int[MAX_N][MAX_N];   // 인접행렬 0과 1

	public static void main(string[] args) {
		
        Scanner sc = new Scanner(System.in);
        vertex = sc.nextInt();
        line = sc.nextInt();
        
        for (int i = 0; i < line; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            Graph[v][u] = Graph[u][v] = 1;
        }
        bfs(0);
    }
    
    
    public static void bfs(int node) {
    	boolean[] visited = new boolean[MAX_N];
        
        Queue<Integer> myqueue = new LinkedList<>();
        visited[node] = true;
        myqueue.add(node);
        
        while(!myqueue.isEmpty()) {
            int curr = myqueue.remove();
            System.out.println(curr + " ");

            for (int next = 0; next < N; next++) {
                if(!visted[next] && Graph[curr][next] != 0) {
                    visited[next] = true;
                    myqueue.add(next);
                }
            }
        }
    }
}

 

 

👉 Shortest path

public class App {

    static final int MAX_N = 10; // 문제에 따라서 최대 노드 개수를 정해줘야 한다.  // 어떤 기준으로 정할까?
    static int[][] D = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};  // 방향 움직이는 2차원 배열
    static int vertex;
    static int[][] Graph = new int[MAX_N][MAX_N];   // 인접행렬 0과 1
    static class Point {
        int row, col, dist;
        Point(int r, int c, int d) {
            row = r; col = c; dist = d;
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        vertex = sc.nextInt();

        for (int i = 0; i < vertex; i++) {
            for (int j = 0; j < vertex; j++) {
            	Graph[i][j] = sc.nextInt();
            }
        }

        int sRow, sCol, dRow, dCol;
        sRow = sc.nextInt(); sCol = sc.nextInt();
        dRow = sc.nextInt(); dCol = sc.nextInt();
        System.out.println(bfs(sRow, sCol, dRow, dCol));
    }
    
    
    public static int bfs(int sRow, int sCol, int dRow, int dCol) {
    	boolean[][] visited = new boolean[MAX_N][MAX_N];
        Queue<Point> myqueue = new LinkedList<>();
        visited[sRow][sCol] = true;
        myqueue.add(new Point(sRow, sCol, 0));  // 시작점 추가
        
        
        while (!myqueue.isEmpty()) {
            Point curr = myqueue.remove();
            if (curr.row == dRow && curr.col == dCol)
            	return curr.dist;


            for (int i = 0; i < 4; i++) {   // 4의 의미는 상하좌우
                int nr = curr.row + D[i][0], nc = curr.col + D[i][1];
                if (nr < 0 || nr > vertex -1 || nc < 0 || nc > vertex - 1) continue; // 상하 좌우 가장자리 체크
                if (visited[nr][nc]) continue;  // 방문 여부 체크
                if (Graph[nr][nc] == 1) continue;   // 배열에서 1은 벽을 의미
                visited[nr][nc] = true;
                myqueue.add(new Point(nr, nc, curr.dist + 1));
            }
        }
        
        return -1;
    }
}