728x90
반응형
가중치가 같을 경우 bfs로 하면 최단거리가 나오지만,
가중치가 다를 경우 dijkstra를 통해 최단거리를 구해야한다.
이 문제는 자칫 보면 조건문의 순서로 문제가 맞고 틀리고가 결정되는 것처럼 보일 수 있다.
나도 이 문제를 풀 때 실수를 했다.
#include <iostream>
#include <vector>
#include <functional>
#include <queue>
using namespace std;
bool visited[100001] = {false};
int directx[] = {1, -1, 2};
int dijkstra(int soobin, int sister){
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
pq.push({0, soobin});
visited[soobin] = true;
while(!pq.empty()){
pair<int,int> node = pq.top();
pq.pop();
if(node.second == sister){
return node.first;
}
for(int i = 0; i < 3; i++){
int dx, thisWeight;
if(i != 0) {
dx = node.second + directx[i];
thisWeight = node.first + 1;
}
else{
dx = node.second * directx[i];
thisWeight = node.first;
}
if(dx >= 0 && dx <= 100000 && !visited[dx]){
visited[dx] = true;
pq.push({thisWeight, dx});
}
}
}
}
int main(void){
int soobin, sister;
cin >> soobin >> sister;
cout << dijkstra(soobin, sister);
}
위의 코드는 틀린 코드이고,
directx[] 배열의 값을 {2, 1, -1} 로 바꾸었더니 맞았다.
왜 맞을까?
백준의 질문 검색을 뒤져보던 중 알게되었다..
+1이나 -1 로 먼저 뒤쪽에 집어넣게 되어 visited 가 true 가 된 숫자는
이미 visited가 true 이기 때문에 *2로 앞쪽에 집어넣어지지 않습니다.
이런 이유로 visited가 true였기 때문에 weight는 갱신되지 않았고, 그래서 계속 틀렸던 것이었다.
참고로 *2의 경우 weight가 0에 해당하니까 갱신되어야만 하는 것이고
만약 weight가 1보다 높은 수였다면 갱신될 필요가 없다.
#include <iostream>
#include <vector>
#include <functional>
#include <queue>
using namespace std;
bool visited[100001] = {false};
int directx[] = {1, -1, 2};
int dijkstra(int soobin, int sister){
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
pq.push({0, soobin});
visited[soobin] = true;
while(!pq.empty()){
pair<int,int> node = pq.top();
pq.pop();
if(node.second == sister){
return node.first;
}
visited[node.second] = true;
for(int i = 0; i < 3; i++){
int dx, thisWeight;
if(i != 0) {
dx = node.second + directx[i];
thisWeight = node.first + 1;
}
else{
dx = node.second * directx[i];
thisWeight = node.first;
}
if(dx >= 0 && dx <= 100000 && !visited[dx]){
pq.push({thisWeight, dx});
}
}
}
}
int main(void){
int soobin, sister;
cin >> soobin >> sister;
cout << dijkstra(soobin, sister);
}
if문에 존재하는 visited위치를 상단으로 올리게 되어도 맞는다.
그렇지만 이 경우, 계속적인 갱신이 되므로 맨위의 코드가 더 빠른 속도로 해결된다.
반응형
'algorithm' 카테고리의 다른 글
[algorithm] 백준 - 모든 순열 (0) | 2020.10.29 |
---|---|
[algorithm] 백준 - 이전 순열 (0) | 2020.10.29 |
[algorithm] 테트로미노 (0) | 2020.10.28 |
[algorithm] 백준 - 다음 순열 (0) | 2020.10.28 |
[algorithm] 최대 공배수, 최소 공배수 (0) | 2020.10.27 |