글 읽기 - 구조체를 이용한 우선순위 큐 동작 좀 봐주세요...

sce9573 4년 전 0

안녕하세요.

방금 전에 숨바꼭질 3 문제를 풀었는데, 구조체를 이용해서 우선순위 큐를 정렬한 것은 '틀렸습니다.'가 뜨고 pair를 사용해서 우선순위 큐를 정렬한 것은 '맞았습니다.'가 뜹니다.

제가 생각하기에 두 결과가 똑같은 것 같은데 아래 두 코드의 차이점을 알 수 있을까요? ㅠㅠ

감사합니다.

// 1. pair를 사용한 우선순위 큐
#include <iostream>
#include <cstdio>
#include <queue>

#define SIZE 100001

using namespace std;

int visit[SIZE];

priority_queue< pair<int, int>, vector< pair<int, int> >, greater< pair<int, int> > > q;
int me;
int sis;

int search() {
	int pos, cnt;

	while (!q.empty()) {
		cnt = q.top().first;
		pos = q.top().second;
		q.pop();

		if (pos == sis) {
			return cnt;
		}

		if (pos * 2 < SIZE) {
			if (visit[pos * 2] == 0) {
				visit[pos * 2] = 1;
				q.push(make_pair(cnt, pos * 2));
			}
		}

		if (pos + 1 < SIZE) {
			if (visit[pos + 1] == 0) {
				visit[pos + 1] = 1;
				q.push(make_pair(cnt + 1, pos + 1));
			}
		}

		if (pos - 1 >= 0) {
			if (visit[pos - 1] == 0) {
				visit[pos - 1] = 1;
				q.push(make_pair(cnt + 1, pos - 1));
			}
		}
	}
}

int main() {
	int T;
	//freopen("13549.txt", "r", stdin);
	setbuf(stdout, NULL);

	scanf("%d %d", &me, &sis);

	visit[me] = 1;
	q.push(make_pair(0, me));

	printf("%d\n", search());

	return 0;
}


// 2. 구조체를 사용한 우선순위 큐
#include <iostream>
#include <cstdio>
#include <queue>

#define SIZE 100001

using namespace std;

int visit[SIZE];

struct node {
	int pos;
	int cnt;
};

struct cmp {
	bool operator() (node a, node b) {
		return a.cnt > b.cnt;
	}
};

priority_queue<node, vector<node>, cmp> q;
int me;
int sis;

int search() {
	int pos, cnt;

	while (!q.empty()) {
		cnt = q.top().cnt;
		pos = q.top().pos;
		q.pop();

		if (pos == sis) {
			return cnt;
		}

		if (pos * 2 < SIZE) {
			if (visit[pos * 2] == 0) {
				visit[pos * 2] = 1;
				q.push({ pos * 2, cnt });
			}
		}

		if (pos + 1 < SIZE) {
			if (visit[pos + 1] == 0) {
				visit[pos + 1] = 1;
				q.push({ pos + 1, cnt + 1 });
			}
		}

		if (pos - 1 >= 0) {
			if (visit[pos - 1] == 0) {
				visit[pos - 1] = 1;
				q.push({ pos - 1, cnt + 1 });
			}
		}
	}
}

int main() {
	int T;
	//freopen("13549.txt", "r", stdin);
	setbuf(stdout, NULL);	

	scanf("%d %d", &me, &sis);

	visit[me] = 1;
	q.push({ me, 0 });

	printf("%d\n", search());

	return 0;
}

clrmt 4년 전 2

당연하겠지만 우선순위 큐는 stable하지 않기 때문에 같은 우선순위를 가진 값은 아무렇게나 들어있습니다. 반면 pair는 첫 번째 값을 기준으로 정렬, 값이 같으면 두 번째 값을 기준으로 정렬해줍니다.

1 6 이라는 값을 넣으면 0회차에서는 1, 2, 4, 8 ... 정상적으로 올라가지만

1회차에서 7과 3이 존재하는데 7을 탐색하는 과정에서 visit[6]을 cnt = 2상태로 미리 먹어버립니다. 같은 1회차에서 3을 탐색할 때 6을 이미 방문했으므로 cnt = 1로 먹지 못하기 때문에 2가 출력되는 문제가 있습니다.

sce9573 4년 전 1

계속 고민했었는데 이런 이유였군요 ㅠㅠ

정말 감사합니다!!!!!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

구조체를 이용한 우선순위 큐 동작 좀 봐주세요...

sce9573 4년 전 0

clrmt 4년 전 2

sce9573 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말