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;
}
'π μκ³ λ¦¬μ¦ > BOJ' μΉ΄ν κ³ λ¦¬μ λ€λ₯Έ κΈ
[C++/BOJ] 11660 : κ΅¬κ° ν© κ΅¬νκΈ° 5 (DP) (0) | 2024.11.17 |
---|---|
[C++/BOJ] 2169 : λ‘λ΄ μ‘°μ’ νκΈ° (DP) (0) | 2023.05.26 |
[C++/BOJ] 1325 : ν¨μ¨μ μΈ ν΄νΉ (BFS/DFS) (1) | 2023.05.14 |
[C++/BOJ] 1012 : μ κΈ°λ λ°°μΆ (BFS/DFS) (0) | 2023.05.12 |
[C++/BOJ] 1417 : κ΅νμμ μ κ±° (μλ£κ΅¬μ‘°) (1) | 2023.05.06 |