99클럽 코테 스터디 5일차 TIL

백준 - 24444번

BFS

• 루트 노드 또는 임의의 노드에서 시작하여 인접한노드를 먼저 탐색하는 방법.
• 시작 정점으로부터 가까운 정점을 먼저 방문하고, 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다.
• 깊게 탐색하기 전에 넓게 탐색하는 것.

정점 A 에 인접한 정점 중 방문하지 않은 정점 B와 C가 있다면

B,C 를 모두 방문하고 방문한 순서대로 큐에 저장한다.

그리고 가장 먼저 저장된 정점 B를 가져와 B의 인접 정점을 탐색하여 방문한다.

큐에 저장된 정점이 없을 때까지 위 과정을 반복한다.

 

스택 프레임을 쌓는 DFS와 달리, 큐를 사용해 메모리를 보다 효율적으로 사용한다.

---

4일차의 DFS 문제에 이어 BFS 문제이다.

그래프 초기화, 간선 입력 등의 코드는 모두 동일하고, dfs 메서드만 변경해주면 될 것 같다.

실패

static void bfs(int r) {
    Queue<Integer> queue = new LinkedList<>();

    visited[visitedIdx++] = r;
    queue.add(r);

    while (!queue.isEmpty()) {
        int x = queue.remove();

        for (int node : graph[x]) {
            if (visited[node] == 0) {
                visited[visitedIdx++] = node;
                queue.add(node);
            }
        }
    }
}

시작 정점	방문할 수 있는 정점
1	2, 4
2	1, 3, 4

 

visited의 배열 크기는 n + 1 로 설정했고, visitedIdx를 증감식으로 표현하여 배열 순서대로 방문 노드 값을 넣고자 했다. 

정점 1에서 인접 정점을 모두 방문하면 visited의 배열 값은 {0, 1, 2, 4, 0, 0} 이다.

문제가 발생하는 곳은 시작 정점 2에서 정점 3을 방문할 때이다.

visited[3] 의 자리에는 이미 방문한 노드 값이 들어와있다. 그렇기 때문에 3을 넣지 않고 조건을 통과해버린다.

결과로는 1, 2, 4, 4, 0 이 출력됐다.

 

가장 결정적인 문제는 visitedIdx였는데, 값으로 들어가야 할 visitedIdx를 배열 위치에 넣고 있었다.

전체 코드

import java.util.*;

public class Main {

    static ArrayList<Integer>[] graph;
    static int[] visited;
    static int visitedIdx = 1;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int m = sc.nextInt();
        int r = sc.nextInt();

        graph = new ArrayList[n + 1];
        visited = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            graph[i] = new ArrayList<>();
        }

        for (int i = 0; i < m; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            graph[u].add(v);
            graph[v].add(u);
        }

        for (int i = 1; i <= n; i++) {
            Collections.sort(graph[i]);
        }

        bfs(r);

        for (int i = 1; i <= n; i++) {
            System.out.println(visited[i]);
        }
        sc.close();
    }

    static void bfs(int r) {
        Queue<Integer> queue = new LinkedList<>();

        visited[r] = visitedIdx++;
        queue.add(r);

        while (!queue.isEmpty()) {
            int x = queue.remove();

            for (int node : graph[x]) {
                if (visited[node] == 0) {
                    visited[node] = visitedIdx++;
                    queue.add(node);
                }
            }
        }
    }
}

---

백준 24444번 알고리즘 수업 - 너비 우선 탐색 1

https://www.acmicpc.net/problem/24444