[BaekJoon] #2644 - 촌수계산 [Java][C++]

문제 링크

---

1. 아이디어

촌수계산은 사람을 노드, 거리를 길이가 1인 간선으로 치환한 그래프에서 두 노드 간 최단 거리를 구하는 것과 동일하다. BFS를 활용해서 촌수를 구하면 된다.

---

2. 복잡도

접근	시간	공간
풀이	$O(N^2)$	$O(N^2)$

($N$ = 입력값 n)

---

3. 코드

풀이 [Java][C++]

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

public class Main {

    static int n;
    static boolean[][] adj;

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

        n = Integer.parseInt(br.readLine());
        adj = new boolean[1 + n][1 + n];

        st = new StringTokenizer(br.readLine());
        int x = Integer.parseInt(st.nextToken());
        int y = Integer.parseInt(st.nextToken());

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

        System.out.println(bfs(x, y));
    }

    static int bfs(int x, int y) {
        Queue<Integer> q = new ArrayDeque<>();
        q.offer(x);

        boolean[] vis = new boolean[1 + n];
        vis[x] = true;

        int dist = 0;

        while (!q.isEmpty()) {
            int sz = q.size();

            while (sz-- > 0) {
                int cur = q.poll();
                if (cur == y) return dist;

                for (int nxt = 1; nxt <= n; nxt++) {
                    if (!adj[cur][nxt] || vis[nxt]) continue;

                    q.offer(nxt);
                    vis[nxt] = true;
                }
            }

            dist++;
        }

        return -1;
    }
}

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

const int MAX_N = 1 + 100;
int n;
bool adj[MAX_N][MAX_N];
bool vis[MAX_N];

int bfs(int x, int y) {
    queue<int> q;
    q.push(x);

    vis[x] = true;

    int dist = 0;

    while (!q.empty()) {
        int sz = q.size();

        while (sz--) {
            int cur = q.front();
            q.pop();

            if (cur == y) return dist;

            for (int nxt = 1; nxt <= n; nxt++) {
                if (!adj[cur][nxt] || vis[nxt]) continue;

                q.push(nxt);
                vis[nxt] = true;
            }
        }

        dist++;
    }

    return -1;
}

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

    int x, y, m;
    cin >> n >> x >> y >> m;

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

    cout << bfs(x, y);
}

---