[BaekJoon] #24446 - 알고리즘 수업 - 너비 우선 탐색 3 [Java][C++]

문제 링크

---

1. 아이디어

양방향 간선들이 주어진 그래프에 대해 너비 우선 탐색을 하면 되는 문제로 인접 리스트를 활용하면 되며, 시작 정점부터의 거리를 구해야 하므로 거리 배열을 활용해 다음 노드의 거리는 이전 노드의 거리에 1을 더하는 방식으로 구현했다.

---

2. 복잡도

접근	시간	공간
풀이	$O(N + E)$	$O(N + E)$

($N$ = 입력값 n, $E$ = 입력값 m)

---

3. 코드

풀이 [Java][C++]

import java.io.*;
import java.util.*;

public class Main {

    static int n;
    static List<Integer>[] adj;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int r = Integer.parseInt(st.nextToken());

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

        while (m-- > 0) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            adj[u].add(v);
            adj[v].add(u);
        }

        System.out.println(bfs(r));
    }

    static String bfs(int start) {
        Queue<Integer> q = new ArrayDeque<>();
        q.offer(start);

        int[] dist = new int[1 + n];
        Arrays.fill(dist, -1);
        dist[start] = 0;

        while (!q.isEmpty()) {
            int cur = q.poll();

            for (int nxt : adj[cur]) {
                if (dist[nxt] != -1) continue;

                q.offer(nxt);
                dist[nxt] = dist[cur] + 1;
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= n; i++) {
            sb.append(dist[i]).append("\n");
        }

        return sb.toString();
    }
}

#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 1 + 100000;
vector<int> adj[MAX_N];
int dist[MAX_N];

void bfs(int start) {
    queue<int> q;
    q.push(start);

    memset(dist, -1, sizeof(dist));
    dist[start] = 0;

    while (!q.empty()) {
        int cur = q.front();
        q.pop();

        for (int nxt : adj[cur]) {
            if (dist[nxt] != -1) continue;

            q.push(nxt);
            dist[nxt] = dist[cur] + 1;
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, m, r;
    cin >> n >> m >> r;

    while (m--) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    bfs(r);

    for (int i = 1; i <= n; i++) {
        cout << dist[i] << '\n';
    }
}

---