[백준] 16118. 달빛 여우 - C++ — 젝무의 개발새발

[Gold I]

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

16118번: 달빛 여우

첫 줄에 나무 그루터기의 개수와 오솔길의 개수를 의미하는 정수 N, M(2 ≤ N ≤ 4,000, 1 ≤ M ≤ 100,000)이 주어진다. 두 번째 줄부터 M개의 줄에 걸쳐 각 줄에 세 개의 정수 a, b, d(1 ≤ a, b ≤ N, a ≠ b

www.acmicpc.net

풀이 1

몇 번째 step인지를 계산하며, 늑대의 경로를 다익스트라로 잘 계산하면 되겠다 싶었지만,

어느 한 그루터기에 조금 늦게 도착하는 경로가 있더라도, 다른 그루터기에 더 빨리 도착할 수 있는 경로가 될 수 있는데, 그것을 무시하므로 WA.

(예제에서, 아래와 같이 계산하면, 늑대 입장에서 2로 가는 거리는 처음에 1이 된다.

그러나, 4로 가는 경로는 1-2-4 (9)보다 1-3-2-4 (7)가 더 빠른데, 1-3-2 경로를 다익스트라 과정에서 무시하므로 실패.)

 #include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
 
#define init cin.tie(0)->ios_base::sync_with_stdio(0);
#define INF 1e9
using namespace std;
typedef pair<int, int> pint;
 
vector<pint> edges[4009];
priority_queue<pint, vector<pint>, greater<pint> > pq;
int dist[4009];    // for fox
pint dist2[4009];  // for wolf
 
int main() {
    init;
    int N, M;
    cin >> N >> M;
 
    // input edges
    int a, b, d;
    for (int i = 0; i < M; i++) {
        cin >> a >> b >> d;
        edges[a].push_back({d, b});
    }
 
    // dijkstra (fox)
    fill(dist, dist + N + 1, INF);
    dist[1] = 0;
    pq.push({0, 1});
 
    while (pq.size()) {
        auto [curd, cur] = pq.top();
        pq.pop();
        if (dist[cur] < curd) continue;
        for (int i = 0; i < edges[cur].size(); i++) {
            auto [nxtd, nxt] = edges[cur][i];
            if (dist[nxt] > curd + nxtd) {
                dist[nxt] = curd + nxtd;
                pq.push({dist[nxt], nxt});
            }
        }
    }
 
    // dijkstra (wolf)
    // dist -> pair<int, int> : first) distance / second) step
    // if step is odd, add half of next dist / if step is even, add twice of next dist.
    for (int i = 1; i < N + 2; i++) {
        dist2[i] = {INF, 0};
    }
    dist2[1] = {0, 0};
    pq.push({0, 1});
 
    while (pq.size()) {
        int curd = pq.top().first;
        int cur = pq.top().second;
        pq.pop();
        if (dist2[cur].first < curd) continue;
        for (int i = 0; i < edges[cur].size(); i++) {
            int nxtd = edges[cur][i].first;
            int nxt = edges[cur][i].second;
            if (dist2[cur].second % 2 == 0) {
                nxtd /= 2;
            } else {
                nxtd *= 2;
            }
            if (dist2[nxt].first > curd + nxtd) {
                dist2[nxt] = {curd + nxtd, dist2[cur].second + 1};
                pq.push({dist2[nxt].first, nxt});
            }
        }
    }
}

풀이 2

우선, 양방향 간선 그래프이므로 (늑대의 경우, 돌아가는 것이 더 나은 결과를 가져올 수 있음)

edge에 양방향 간선을 추가해 줌.

int dist2[4009][2]; // for wolf

또한, 위와 같이 짝수 번째 step에 도달하는 최소 dist와 홀수 번째 step에 도달하는 최소 dist를 따로 저장.

(각자 짝수 번째와 홀수 번째 step에 도달하는 것은 최소 dist로 고정하고, 더 높은 dist가 갱신되려 할 때 무시해도 되는 이유가 - 각각 다음 그루터기로 나아갈 때, 1/2을 할 지, *2를 할 지가 고정되어 있기 때문에, 이렇게 저장해도 무방함.)

또한, 아래와 같이 pair<int, pair<int, int>> 를 이용한 Priority Queue로, 몇 번째 step으로 queue에 push되었는 지 확인하여, *2를 할 지, 1/2를 할 지, 그리고 어느 index에 dist를 갱신할 지 나눈다.

 typedef pair<int, pair<int, int>> ppint;
 
priority_queue<ppint, vector<ppint>, greater<ppint>> pq2;

마지막으로, 거리가 정수형이기 때문에, /2 를 할 때 부동소수점수 타입으로 바꿔주지 않는 이상, 그대로 제출하면 예제는 맞지만 WA가 나온다. 아래와 같이 간선을 초기화할 때 거리를 두 배로 계산하는 것을 추천.

 edges[a].push_back({d * 2, b});
edges[b].push_back({d * 2, a});

AC.

 #include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
 
#define init cin.tie(0)->ios_base::sync_with_stdio(0);
#define INF 1e9
using namespace std;
typedef pair<int, int> pint;
typedef pair<int, pair<int, int>> ppint;
 
vector<pint> edges[4009];
priority_queue<pint, vector<pint>, greater<pint>> pq;
priority_queue<ppint, vector<ppint>, greater<ppint>> pq2;
int dist[4009];      // for fox
int dist2[4009][2];  // for wolf
 
int main() {
    init;
    int N, M;
    cin >> N >> M;
 
    // input edges
    int a, b, d;
    for (int i = 0; i < M; i++) {
        cin >> a >> b >> d;
        edges[a].push_back({d * 2, b});
        edges[b].push_back({d * 2, a});
    }
 
    // dijkstra (fox)
    fill(dist, dist + N + 1, INF);
    dist[1] = 0;
    pq.push({0, 1});
 
    while (pq.size()) {
        auto [curd, cur] = pq.top();
        pq.pop();
        if (dist[cur] < curd) continue;
        for (int i = 0; i < edges[cur].size(); i++) {
            auto [nxtd, nxt] = edges[cur][i];
            if (dist[nxt] > curd + nxtd) {
                dist[nxt] = curd + nxtd;
                pq.push({dist[nxt], nxt});
            }
        }
    }
 
    // dijkstra (wolf)
    // dist2[i][0] -> even step's dist (next step 1/2) / dist2[i][1] -> odd step's dist (next step *2)
    for (int i = 1; i < N + 2; i++) {
        dist2[i][0] = INF;
        dist2[i][1] = INF;
    }
    dist2[1][0] = 0;
 
    pq2.push({0, {1, 0}});
    while (pq2.size()) {
        int curd = pq2.top().first;
        int cur = pq2.top().second.first;
        int step = pq2.top().second.second;
        pq2.pop();
        if (step % 2 == 0) {
            if (dist2[cur][0] < curd) continue;
        } else {
            if (dist2[cur][1] < curd) continue;
        }
        for (int i = 0; i < edges[cur].size(); i++) {
            int nxtd = edges[cur][i].first;
            int nxt = edges[cur][i].second;
            if (step % 2 == 0) {
                nxtd /= 2;
                if (dist2[nxt][1] > curd + nxtd) {
                    dist2[nxt][1] = curd + nxtd;
                    pq2.push({dist2[nxt][1], {nxt, step + 1}});
                }
            } else {
                nxtd *= 2;
                if (dist2[nxt][0] > curd + nxtd) {
                    dist2[nxt][0] = curd + nxtd;
                    pq2.push({dist2[nxt][0], {nxt, step + 1}});
                }
            }
        }
    }
 
    int result = 0;
    for (int i = 1; i < N + 1; i++) {
        if (dist[i] < min(dist2[i][0], dist2[i][1])) result++;
    }
    cout << result;
}

풀이 1
풀이 2

내 블로그 - 관리자 홈 전환	`Q` `Q`
새 글 쓰기	`W` `W`

글 수정 (권한 있는 경우)	`E` `E`
댓글 영역으로 이동	`C` `C`

이 페이지의 URL 복사	`S` `S`
맨 위로 이동	`T` `T`
티스토리 홈 이동	`H` `H`
단축키 안내	`Shift` + `/` `⇧` + `/`

[백준] 16118. 달빛 여우 - C++

풀이 1

풀이 2

티스토리툴바

단축키

내 블로그

블로그 게시글

모든 영역

	#include <algorithm>
	#include <iostream>
	#include <queue>
	#include <vector>

	#define init cin.tie(0)->ios_base::sync_with_stdio(0);
	#define INF 1e9
	using namespace std;
	typedef pair<int, int> pint;

	vector<pint> edges[4009];
	priority_queue<pint, vector<pint>, greater<pint> > pq;
	int dist[4009]; // for fox
	pint dist2[4009]; // for wolf

	int main() {
	init;
	int N, M;
	cin >> N >> M;

	// input edges
	int a, b, d;
	for (int i = 0; i < M; i++) {
	cin >> a >> b >> d;
	edges[a].push_back({d, b});
	}

	// dijkstra (fox)
	fill(dist, dist + N + 1, INF);
	dist[1] = 0;
	pq.push({0, 1});

	while (pq.size()) {
	auto [curd, cur] = pq.top();
	pq.pop();
	if (dist[cur] < curd) continue;
	for (int i = 0; i < edges[cur].size(); i++) {
	auto [nxtd, nxt] = edges[cur][i];
	if (dist[nxt] > curd + nxtd) {
	dist[nxt] = curd + nxtd;
	pq.push({dist[nxt], nxt});
	}
	}
	}

	// dijkstra (wolf)
	// dist -> pair<int, int> : first) distance / second) step
	// if step is odd, add half of next dist / if step is even, add twice of next dist.
	for (int i = 1; i < N + 2; i++) {
	dist2[i] = {INF, 0};
	}
	dist2[1] = {0, 0};
	pq.push({0, 1});

	while (pq.size()) {
	int curd = pq.top().first;
	int cur = pq.top().second;
	pq.pop();
	if (dist2[cur].first < curd) continue;
	for (int i = 0; i < edges[cur].size(); i++) {
	int nxtd = edges[cur][i].first;
	int nxt = edges[cur][i].second;
	if (dist2[cur].second % 2 == 0) {
	nxtd /= 2;
	} else {
	nxtd *= 2;
	}
	if (dist2[nxt].first > curd + nxtd) {
	dist2[nxt] = {curd + nxtd, dist2[cur].second + 1};
	pq.push({dist2[nxt].first, nxt});
	}
	}
	}
	}

	typedef pair<int, pair<int, int>> ppint;

	priority_queue<ppint, vector<ppint>, greater<ppint>> pq2;

	edges[a].push_back({d * 2, b});
	edges[b].push_back({d * 2, a});