[백준 2644] 촌수계산 (C++/Python)

C++)

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#define MAX_NUM 101
using namespace std;

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

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

	vector<vector<int>> v(n + 1);

	cin >> m;
	for (int i = 0; i < m; i++) {
		cin >> x >> y;

		v[x].push_back(y);
		v[y].push_back(x);
	}

	int visited[MAX_NUM];
	fill(visited, visited + MAX_NUM, -1);

	queue<int> q;
	visited[a] = 0;
	q.push(a);

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

		for (int i = 0; i < v[cur].size(); i++) {
			int next = v[cur][i];

			if (visited[next] == -1) {
				visited[next] = visited[cur]+1;

				if (next == b)
					break;
				q.push(next);
			}
		}
	}

	cout << visited[b];

	return 0;
}

 

 

 

Python)

import sys
from collections import deque

read = sys.stdin.readline

n = int(read().rstrip())
a, b = map(int, read().rstrip().split())
m = int(read().rstrip())

arr = [ [] for _ in range(n+1)]
visited = [-1] * (n+1)

for _ in range(m):
    x, y = map(int, read().rstrip().split())

    arr[x].append(y)
    arr[y].append(x)

q = deque()
visited[a] = 0
q.append(a)

while q:
    cur = q.popleft()

    for next in arr[cur]:
        if visited[next] == -1:
            visited[next] = visited[cur] + 1
            
            if next == b:
                break
            
            q.append(next)

print(visited[b])