반응형
포인트
1. bfs() 를 잘 알고 있는가?
2. bfs는 모든 노드를 지날때 같은 가중치를 같는 노드만 탐색을 할 수 있다. 이에 dequeue 를 사용을 하여 가중치를 다르게 처리를 하여 bfs 를 진행할 수 있도록 한다.
🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다.
#include <iostream>
#include <deque>
#include <cstring>
using namespace std;
int n, m;
int dist[100001];
void bfs() { // bfs 는 모든 노드로 가는 가중치가 1인 경우나 같은 경우이다.
// 지금 문제는 하나의 가중치가 다름으로 다르게 처리를 해야 한다.
deque<int> q;
q.push_back(n);
dist[n] = 0;
while (!q.empty()) {
int x = q.front(); // 가중치가 0이기 때문에 앞으로 꺼낸다.
q.pop_front();
if (x == m) {
cout << dist[m] << '\n';
return;
}
if (2 * x < 100001 && dist[2 * x] == -1) { // 가중치 0
q.push_front(2 * x);
dist[2 * x] = dist[x];
}
if (x - 1 >= 0 && dist[x - 1] == -1) { // 가중치 1
q.push_back(x - 1);
dist[x - 1] = dist[x] + 1;
}
if (x + 1 < 100001 && dist[x + 1] == -1) { //가중치 1
q.push_back(x + 1);
dist[x + 1] = dist[x] + 1;
}
}
}
int main() {
cin >> n >> m;
memset(dist, -1, sizeof(dist));
bfs();
return 0;
}
반응형
'알고리즘' 카테고리의 다른 글
[알고리즘] c++ cpp 연구소시리즈 (연구소2) (0) | 2020.10.05 |
---|---|
[알고리즘] c++ cpp 숨바꼭질 시리즈 (숨박꼭질4) (0) | 2020.10.04 |
[알고리즘] c++ cpp 숨바꼭질 시리즈 (숨바꼭질2) (0) | 2020.10.04 |
[알고리즘] c++ cpp 숨바꼭질 시리즈 (숨바꼭질1) (0) | 2020.10.04 |
[알고리즘] c++, cpp 플로이드 와샬 (0) | 2020.09.26 |
댓글