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

문제 링크

---

1. 문제 풀이

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

---

2. 코드

1. 풀이 [Java]

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

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

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

        st = new StringTokenizer(br.readLine());
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());

        int m = Integer.parseInt(br.readLine());
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            adj[x][y] = adj[y][x] = true;
        }

        int dist = bfs(a, b, n, adj);
        System.out.println(dist);
    }

    static int bfs(int a, int b, int n, boolean[][] adj) {
        Queue<Integer> q = new ArrayDeque<>();
        q.offer(a);

        boolean[] visited = new boolean[1 + n];
        visited[a] = true;

        int dist = 0;

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

            while (size-- > 0) {
                int node = q.poll();
                if (node == b) return dist;

                for (int next = 1; next <= n; next++) {
                    if (adj[node][next] && !visited[next]) {
                        q.offer(next);
                        visited[next] = true;
                    }
                }
            }

            dist++;
        }

        return -1;
    }
}

2. 풀이 [C++]

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

int n;
bool adj[1 + 100][1 + 100];
bool visited[1 + 100];

int bfs(int a, int b) {
    queue<int> q;
    q.push(a);

    visited[a] = true;

    int dist = 0;

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

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

            if (node == b) return dist;

            for (int next = 1; next <= n; next++) {
                if (adj[node][next] && !visited[next]) {
                    q.push(next);
                    visited[next] = true;
                }
            }
        }

        dist++;
    }

    return -1;
}

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

    int a, b, m;
    cin >> n >> a >> b >> m;

    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        adj[x][y] = adj[y][x] = true;
    }

    int cnt = bfs(a, b);
    cout << cnt;
}

---