백준 2644 촌수계산 (c++) : 피너클

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

2644번: 촌수계산

브루트포스를 이용해 풀었다.

int n, m; 
int a, b;

bool visited[101];
vector<int> v[101];

사용할 변수다.

cin >> n;
cin >> a >> b;
cin >> m;
memset(visited, false, sizeof(visited));
for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    v[a].push_back(b);
    v[b].push_back(a);
}

값들을 입력받고 visited를 초기화한다.

queue<pair<int, int>> q;
q.push({ a, 0 });
visited[a] = true;
int a = -1;

bfs를 준비한다.

int a에는 정답을 담을 것이다. bfs에서 답이 나오지 않는다면 -1이 그대로 출력될것이다.

while (!q.empty()) {
    int now = q.front().first;
    int ans = q.front().second;
    q.pop();

q가 차있는동안 반복문을 돌리며 now와 ans를 구하고 pop한다.

ans는 현재 이동한 촌수다.

    if (now == b) {
        a = ans;
        break;
    }

만약 now == b라면 a에 ans를 넣고 반복문을 나온다.

    for (int i = 0; i < v[now].size(); i++) {
        int next = v[now][i];
        if (!visited[next]) {
            q.push({ next, ans + 1 });
            visited[next] = true;
        }
    }
}
cout << a << '\n';

그후 now와 연결되어있으면서 방문하지 않은 곳을 q에 넣어주고 visited처리해주면 된다.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>

using namespace std;

int n, m; 
int a, b;

bool visited[101];
vector<int> v[101];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n;
	cin >> a >> b;
	cin >> m;
	memset(visited, false, sizeof(visited));
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		v[a].push_back(b);
		v[b].push_back(a);
	}

	queue<pair<int, int>> q;
	q.push({ a, 0 });
	visited[a] = true;
	int a = -1;
	while (!q.empty()) {
		int now = q.front().first;
		int ans = q.front().second;
		q.pop();
		if (now == b) {
			a = ans;
			break;
		}

		for (int i = 0; i < v[now].size(); i++) {
			int next = v[now][i];
			if (!visited[next]) {
				q.push({ next, ans + 1 });
				visited[next] = true;
			}
		}
	}
	cout << a << '\n';
}

전체코드다.