λ³Έλ¬Έ λ°”λ‘œκ°€κΈ°

πŸ“ μ•Œκ³ λ¦¬μ¦˜/BOJ

[C++/BOJ] 2644 : μ΄Œμˆ˜κ³„μ‚° (λ‹€μ΅μŠ€νŠΈλΌ)

728x90

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

문제

우리 λ‚˜λΌλŠ” κ°€μ‘± ν˜Ήμ€ μΉœμ²™λ“€ μ‚¬μ΄μ˜ 관계λ₯Ό μ΄Œμˆ˜λΌλŠ” λ‹¨μœ„λ‘œ ν‘œν˜„ν•˜λŠ” λ…νŠΉν•œ λ¬Έν™”λ₯Ό 가지고 μžˆλ‹€. μ΄λŸ¬ν•œ μ΄Œμˆ˜λŠ” λ‹€μŒκ³Ό 같은 λ°©μ‹μœΌλ‘œ κ³„μ‚°λœλ‹€. 기본적으둜 λΆ€λͺ¨μ™€ μžμ‹ 사이λ₯Ό 1촌으둜 μ •μ˜ν•˜κ³  μ΄λ‘œλΆ€ν„° μ‚¬λžŒλ“€ κ°„μ˜ 촌수λ₯Ό κ³„μ‚°ν•œλ‹€. 예λ₯Ό λ“€λ©΄ λ‚˜μ™€ 아버지, 아버지와 ν• μ•„λ²„μ§€λŠ” 각각 1촌으둜 λ‚˜μ™€ ν• μ•„λ²„μ§€λŠ” 2촌이 되고, 아버지 ν˜•μ œλ“€κ³Ό ν• μ•„λ²„μ§€λŠ” 1촌, λ‚˜μ™€ 아버지 ν˜•μ œλ“€κ³ΌλŠ” 3촌이 λœλ‹€.

μ—¬λŸ¬ μ‚¬λžŒλ“€μ— λŒ€ν•œ λΆ€λͺ¨ μžμ‹λ“€ κ°„μ˜ 관계가 μ£Όμ–΄μ‘Œμ„ λ•Œ, 주어진 두 μ‚¬λžŒμ˜ 촌수λ₯Ό κ³„μ‚°ν•˜λŠ” ν”„λ‘œκ·Έλž¨μ„ μž‘μ„±ν•˜μ‹œμ˜€.

μž…λ ₯

μ‚¬λžŒλ“€μ€ 1, 2, 3, …, n (1 ≤ n ≤ 100)의 μ—°μ†λœ 번호둜 각각 ν‘œμ‹œλœλ‹€. μž…λ ₯ 파일의 첫째 μ€„μ—λŠ” 전체 μ‚¬λžŒμ˜ 수 n이 주어지고, λ‘˜μ§Έ μ€„μ—λŠ” 촌수λ₯Ό 계산해야 ν•˜λŠ” μ„œλ‘œ λ‹€λ₯Έ 두 μ‚¬λžŒμ˜ λ²ˆν˜Έκ°€ 주어진닀. 그리고 μ…‹μ§Έ μ€„μ—λŠ” λΆ€λͺ¨ μžμ‹λ“€ κ°„μ˜ κ΄€κ³„μ˜ 개수 m이 주어진닀. λ„·μ§Έ μ€„λΆ€ν„°λŠ” λΆ€λͺ¨ μžμ‹κ°„μ˜ 관계λ₯Ό λ‚˜νƒ€λ‚΄λŠ” 두 번호 x,yκ°€ 각 쀄에 λ‚˜μ˜¨λ‹€. μ΄λ•Œ μ•žμ— λ‚˜μ˜€λŠ” 번호 xλŠ” 뒀에 λ‚˜μ˜€λŠ” μ •μˆ˜ y의 λΆ€λͺ¨ 번호λ₯Ό λ‚˜νƒ€λ‚Έλ‹€.

각 μ‚¬λžŒμ˜ λΆ€λͺ¨λŠ” μ΅œλŒ€ ν•œ λͺ…λ§Œ 주어진닀.

좜λ ₯

μž…λ ₯μ—μ„œ μš”κ΅¬ν•œ 두 μ‚¬λžŒμ˜ 촌수λ₯Ό λ‚˜νƒ€λ‚΄λŠ” μ •μˆ˜λ₯Ό 좜λ ₯ν•œλ‹€. μ–΄λ–€ κ²½μš°μ—λŠ” 두 μ‚¬λžŒμ˜ μΉœμ²™ 관계가 μ „ν˜€ μ—†μ–΄ 촌수λ₯Ό 계산할 수 없을 λ•Œκ°€ μžˆλ‹€. μ΄λ•Œμ—λŠ” -1을 좜λ ₯ν•΄μ•Ό ν•œλ‹€.


 

싀버2.

bfs ν˜•μ‹μœΌλ‘œ ν’€ 수 μžˆλŠ”? λ‹€μ΅μŠ€νŠΈλΌ λ¬Έμ œμ΄λ‹€

μš°μ„ μˆœμœ„ 큐λ₯Ό μ‚¬μš©ν•˜μ—¬ ν’€ 수 μžˆλ‹€

 

 

λ‚˜μ˜ 풀이

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int n, x, y, q, w, m;
int d[102];
int visited[102];
int main() {
	cin >> n >> x >> y >> m;
	vector<vector<int>> a(n + 1);
	priority_queue<pair<int, int>> p;
	while(m--) {
		cin >> q >> w;
        a[q].push_back(w);
        a[w].push_back(q);
    }
	fill(d, d + n + 1, 101);
	d[x] = 0;
    p.push({0, x});
    // bfs
    while (!p.empty()){
        int nw = p.top().second;
		p.pop();
		if (visited[nw]) continue;
		visited[nw] = true;
		for (auto t : a[nw]) {
			if (d[t] > d[nw] + 1) {
				d[t] = d[nw] + 1;
                p.push({-d[t], t});
            }
        }
    }
    if (d[y] == 101) d[y] = -1;
	cout << d[y] << endl;
}

 

728x90