[TIL] 99클럽 코테 스터디 5일차 TIL + 백준 24444 너비 우선 탐색 1

 

문제 풀이

 

문제 탐색하기

너비 우선 탐색(BFS, Breadth-First Search) ?

그래프 탐색 알고리즘으로, 너비를 우선으로 하여 탐색을 진행합니다. 시작 노드에서 가까운 노드를 우선적으로 탐색하며, 동일 레벨에 있는 노드를 모두 탐색한 후 다음 레벨로 넘어가는 방식입니다. BFS는 일반적으로 큐(Queue) 자료 구조를 사용하여 구현합니다.

 

BFS의 동작 원리

1. 시작 노드를 큐에 삽입하고 방문 처리를 합니다.
2. 큐에서 노드를 하나씩 꺼내 해당 노드의 이웃 노드를 모두 큐에 추가합니다. 추가할 때 이웃 노드가 방문되지 않은 경우만 추가합니다.
3. 위 과정을 큐가 빌 때까지 반복합니다.

BFS의 주요 특징

• 시간 복잡도: O(V + E) (V: 정점 수, E: 간선 수)로 그래프의 모든 노드를 탐색합니다.
• 장점: 최단 경로를 찾는 문제에 적합하며, 경로 탐색에서 DFS와 달리 특정 노드까지의 최단 거리를 보장합니다.
• 단점: DFS보다 메모리 사용량이 많을 수 있습니다. 넓은 범위를 우선 탐색하므로 큐에 많은 노드가 쌓일 수 있기 때문입니다.

BFS의 활용 예시

BFS는 최단 경로 찾기, 레벨 순회, 최소 이동 비용 계산 등 최단 거리나 계층 구조 탐색이 필요한 문제에 적합합니다.

 

 

BFS 알고리즘을 활용하여 문제 설계하기

문제에 주어진 예제를 이용하여 BFS 알고리즘을 이해하고 문제 풀이를 설계해보겠습니다.

예제는 아래와 같습니다. 

5 5 1 (정점 N : 5 / 간선M : 5 / 시작 점 R : 1 )
1 4
1 2
2 3
2 4
3 4

 

정점 1하고 인접한 2, 4를 탐색하며 처음 방문하는 노드이기 때문에 큐에 2, 4를 추가합니다.

더 이상 방문할 노드가 없는 경우 dequeue 하여 나오는 정점에서 재 탐색합니다.

정점 2는 3하고 4를 방문할 수 있지만 4는 기존에 방문했던 노드이기때문에 큐에 추가하지 않고

3만 추가해줍니다.

dequeue 과정을 반복하여 정점 4에서 방문할 수 있는 노드는 1하고 2이며 이 둘다 방문했던 노드라서 정점 3으로 넘어가줍니다.

이렇게 queue가 모두 비워지게 되면 탐색을 종료하게 됩니다.

 

위의 과정을 통해서 각 정점이 몇번째에 탐색을 하게 되는지를 구하면 되는 문제입니다.

 

 

문제 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {

    static boolean[] visited; // 방문 여부 저장 배열
    static LinkedList<Integer> queue = new LinkedList<>(); // bfs queue
    static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>(); // graph 저장 arraylist
    static int[] turn; // 각 정점의 방문 순서 저장 배열

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int R = Integer.parseInt(st.nextToken());

        visited = new boolean[N+1];
        turn = new int[N+1];

        for(int i=0; i<=N; i++){
            graph.add(new ArrayList<>());
        }

        for(int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());

            graph.get(u).add(v);
            graph.get(v).add(u);
        }

        for(int i=1; i<=N; i++){
            Collections.sort(graph.get(i));
        }

        bfs(R);
        for(int i=1; i<turn.length; i++){
            System.out.println(turn[i]);
        }
    }

    private static void bfs(int R){
        queue.offer(R);
        visited[R] = true;

        int chk = 1;
        while(!queue.isEmpty()){
            int x = queue.poll();
            turn[x] = chk++;

            for(int i=0; i<graph.get(x).size(); i++){
                int visit = graph.get(x).get(i);
                if(!visited[visit]){
                    queue.offer(visit);
                    visited[visit] = true;
                }
            }
        }

    }

}

 

 

오늘의 회고

어제의 DFS알고리즘에 이어 BFS알고리즘 까지 알아갈 수 있어서 좋았습니다.

어제와 비슷한 방식으로 틀을 잡고 BFS알고리즘을 공부해서 적용하니 풀 수 있었습니다.

하지만 비슷한 문제들을 여러번 풀어봐야 익숙해질 것 같슴미다.... 파이팅