백준 2644 - 촌수계산(C++)

문제 링크입니다. https://www.acmicpc.net/problem/2644

2644번: 촌수계산

간단한 그래프 문제였습니다.

문제 조건

출력 예시

X -> Y 까지 가는데 거쳐가야하는 수를 구하는 문제였습니다.

예시를 통해 확인해보겠습니다.

7 -> 3 을 가는데 7 -> 2 -> 1 -> 3 으로 이동할 수 있습니다. 따라서 촌수가 3이 됩니다.

 

M개의 line이 주어졌을때, X와 Y를 서로 양방향으로 저장해줍니다.

시작점을 queue에 넣어준 뒤, 갈 수 있는 점들을 확인합니다. 

위와 같은 과정을 계속 반복하면서 도착점에 도착했을 때, 이동 횟수를 출력해줍니다.

 

 

문제 접근 방법

1. M개의 선이 주어질때, X와 Y점을 양방향으로 저장해줍니다.

2. 시작점에서 시작해, 갈 수 있는 곳을 확인해봅니다.

3. 도착점에 도달했을 경우 이동 횟수를 return 해줍니다.

4. 탐색이 끝났는데도 도착하지 못했다면 -1을 return 해줍니다.

 

 

자세한 것은 코드를 참고해주세요.

#define _CRT_SECURE_NO_WARNINGS
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <string>
#include <deque>

using namespace std;

int N, M;
int start, finish;
int check[101];
vector<int> line[101];

int bfs() {
	queue<pair<int,int>> q;
	q.push(make_pair(start,0));
	check[start] = 1;
	while (!q.empty()) {
		int x = q.front().first;
		int cnt = q.front().second;
		q.pop();
		if (x == finish) {
			return cnt;
		}
		for (int i = 0; i < line[x].size(); i++) {
			int xx = line[x][i];
			if (check[xx] == 0) {
				check[xx] = 1;
				q.push(make_pair(xx, cnt + 1));
			}
		}
	}
	return -1;
}

void solve() {
	int ans = bfs();
	cout << ans;
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N;
	cin >> start >> finish;
	cin >> M;
	for (int i = 0; i < M; i++) {
		int x, y;
		cin >> x >> y;
		line[x].push_back(y);
		line[y].push_back(x);
	}
	solve();
	return 0;
}

 

 

질문 및 조언 댓글 남겨주세요!