글 읽기 - 도저히 어디가 틀린지 모르겠네요...주석있어요!!

qwq713 6년 전 0

어디가 틀렸는지 아에 모르겠네요...

단순히 연결되어있으면 bfs 시작된 횟수만큼 (bfs가 시작되면 인접한 노드 모드 색칠(true)됨)

return해주면 된다고 생각했는데 .... 아무리봐도모르겠네요 ㅠ 문제진행은 50%까지 됩니다.ㅜ

#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#include<algorithm>
using namespace std;

typedef struct enermy {
	int y;
	int x;
	int radius;
}enermy;

void resetArr(bool * check, int n);			//check초기화해주는함수
double cal_distance(enermy e1, enermy e2);	//두 적 간의 거리 계산해주는 함수
bool is_connected(enermy e1, enermy e2);	//두 적이 연결되어있는지 확인해주는 함수
void bfs(int point);						//bfs 탐색 알고리즘 함수.

vector<int> list[3000];
bool check[3000];

int main(void) {
	int T;
	cin >> T;
		while (T--) {
			int cnt = 1;
			int N;
			cin >> N;
			vector<enermy> enermies;
			for (int i = 0; i < N; i++) {
				int tempX;
				int tempY;
				int tempR;
				cin >> tempX >> tempY >> tempR;
				enermy temp_enermy = { tempY,tempX,tempR };
				enermies.push_back(temp_enermy);
			}
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (i != j) {
						if (is_connected(enermies[i], enermies[j])) { //연결되어있으면 linked_list형식으로 추가해줌.
							list[i].push_back(j);
							list[j].push_back(i);
						}
					}
				}
			}
			for (int i = 0; i < N; i++) {
				if (check[i] == false) { //bfs시작된 횟수만큼 그룹의 수가 존재.
					bfs(i);
					cnt++;
				}
			}
			for (int i = 0; i < N; i++) { 
				for (int j = 0; j < list[i].size(); j++) {
					list[i].pop_back();
				}
			}
			//reset vector.

			resetArr(check, N);
			//reset checkArr
		cout << cnt - 1 << endl;
	}
	return 0;
}

double cal_distance(enermy e1, enermy e2) {
	double distance = sqrt((e1.x - e2.x)*(e1.x - e2.x) + (e1.y - e2.y)*(e1.y - e2.y));
	return distance;
}
bool is_connected(enermy e1, enermy e2) {
	double sumRadius = e1.radius + e2.radius;
	if (sumRadius >= cal_distance(e1, e2)) {
		return true;
	}
	else {
		return false;
	}
}

void resetArr(bool * check, int n) {
	for (int i = 1; i <= n; i++) {
		check[i] = false;
	}
}

void bfs(int point) {
	queue<int> q;
	q.push(point);
	check[point] = true;

	while (!q.empty()) {
		int now = q.front();
		q.pop();
		for (int i = 0; i < list[now].size(); i++) {
			int nextpoint = list[now][i];
			if (check[nextpoint] == false) {
				q.push(nextpoint);
				check[nextpoint] = true;
			}
		}
	}
}

djm03178 6년 전 1

resetArr이 0은 안 지우고 자칫하면 배열 범위를 벗어난 3000을 지웁니다.

qwq713 6년 전 0

헉. 재활용했다가 이런 문..제가.. 감사합니다 빠르게돌려보겠습니다 !!

qwq713 6년 전 0

그래도 오류가 뜨네요 코드 다시한번 읽어봤는데 어디에서 문제가 생기는지 감이 안오네요 ..

#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#include<algorithm>
using namespace std;

typedef struct enermy {
	int y;
	int x;
	int radius;
}enermy;

void resetArr(bool * check, int n);			//check초기화해주는함수
double cal_distance(enermy e1, enermy e2);	//두 적 간의 거리 계산해주는 함수
bool is_connected(enermy e1, enermy e2);	//두 적이 연결되어있는지 확인해주는 함수
void bfs(int point);						//bfs 탐색 알고리즘 함수.

vector<int> list[3000];
bool check[3000];

int main(void) {
	ios_base::sync_with_stdio(false);
	int T;
	cin >> T;
		while (T--) {
			int cnt = 1;
			int N;
			cin >> N;
			vector<enermy> enermies;
			for (int i = 0; i < N; i++) {
				int tempX;
				int tempY;
				int tempR;
				cin >> tempX >> tempY >> tempR;
				enermy temp_enermy = { tempY,tempX,tempR };
				enermies.push_back(temp_enermy);
			}
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (i != j) {
						if (is_connected(enermies[i], enermies[j])) { //연결되어있으면 linked_list형식으로 추가해줌.
							list[i].push_back(j);
							list[j].push_back(i);
						}
					}
				}
			}
			for (int i = 0; i < N; i++) {
				if (check[i] == false) { //bfs시작된 횟수만큼 그룹의 수가 존재.
					bfs(i);
					cnt++;
				}
			}
			for (int i = 0; i < N; i++) { 
				for (int j = 0; j < list[i].size(); j++) {
					list[i].pop_back();
				}
			}
			//reset vector.

			resetArr(check, N-1);
			//reset checkArr
		cout << cnt - 1 << endl;
	}
	return 0;
}

double cal_distance(enermy e1, enermy e2) {
	double distance = sqrt((e1.x - e2.x)*(e1.x - e2.x) + (e1.y - e2.y)*(e1.y - e2.y));
	return distance;
}
bool is_connected(enermy e1, enermy e2) {
	double sumRadius = e1.radius + e2.radius;
	if (sumRadius >= cal_distance(e1, e2)) {
		return true;
	}
	else {
		return false;
	}
}

void resetArr(bool * check, int n) {
	for (int i = 0; i < n; i++) {
		check[i] = false;
	}
}

void bfs(int point) {
	queue<int> q;
	q.push(point);
	check[point] = true;

	while (!q.empty()) {
		int now = q.front();
		q.pop();
		for (int i = 0; i < list[now].size(); i++) {
			int nextpoint = list[now][i];
			if (check[nextpoint] == false) {
				q.push(nextpoint);
				check[nextpoint] = true;
			}
		}
	}
}

djm03178 6년 전 1

55번째 줄이 잘못되었습니다. size는 조건을 검사할 때마다 호출되므로 루프를 돌 때마다 줄어들어 결국 원소를 다 없애기 전에 j가 더 커지게 됩니다.

이렇게 하지 말고 그냥 list[i].clear(); 를 하면 됩니다.

djm03178 6년 전 1

여담으로, 적을 의미하는 영단어는 r이 없는 enemy 입니다.

qwq713 6년 전 0

아에 로직이 잘못되었나봐요.

제 생각에는 68라인에 sqrt 함수 쓰면서 소수점에서 값이 어긋날수도 있다고 생각하는데

이부분은 신경쓰지 않아도 되는 부분인가요?

#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#include<algorithm>
using namespace std;

typedef struct enemy {
	int y;
	int x;
	int radius;
}enemy;

void resetArr(bool * check, int n);			//check초기화해주는함수
double cal_distance(enemy e1, enemy e2);	//두 적 간의 거리 계산해주는 함수
bool is_connected(enemy e1, enemy e2);	//두 적이 연결되어있는지 확인해주는 함수
void bfs(int point);						//bfs 탐색 알고리즘 함수.

vector<int> list[3000];
bool check[3000];

int main(void) {
	ios_base::sync_with_stdio(false);
	int T;
	cin >> T;
		while (T--) {
			int cnt = 1;
			int N;
			cin >> N;
			vector<enemy> enemies;
			for (int i = 0; i < N; i++) {
				int tempX;
				int tempY;
				int tempR;
				cin >> tempX >> tempY >> tempR;
				enemy temp_enermy = { tempY,tempX,tempR };
				enemies.push_back(temp_enermy);
			}
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (i != j) {
						if (is_connected(enemies[i], enemies[j])) { //연결되어있으면 linked_list형식으로 추가해줌.
							list[i].push_back(j);
							list[j].push_back(i);
						}
					}
				}
			}
			for (int i = 0; i < N; i++) {
				if (check[i] == false) { //bfs시작된 횟수만큼 그룹의 수가 존재.
					bfs(i);
					cnt++;
				}
			}
			for (int i = 0; i < N; i++) { 
				list[i].clear();
			}
			//reset vector.

			resetArr(check, N-1);
			//reset checkArr
		cout << cnt - 1 << endl;
	}
	return 0;
}

double cal_distance(enemy e1, enemy e2) {
	double distance = sqrt((e1.x - e2.x)*(e1.x - e2.x) + (e1.y - e2.y)*(e1.y - e2.y));
	return distance;
}
bool is_connected(enemy e1, enemy e2) {
	double sumRadius = e1.radius + e2.radius;
	if (sumRadius >= cal_distance(e1, e2)) {
		return true;
	}
	else {
		return false;
	}
}

void resetArr(bool * check, int n) {
	for (int i = 0; i < n; i++) {
		check[i] = false;
	}
}

void bfs(int point) {
	queue<int> q;
	q.push(point);
	check[point] = true;

	while (!q.empty()) {
		int now = q.front();
		q.pop();
		for (int i = 0; i < list[now].size(); i++) {
			int nextpoint = list[now][i];
			if (check[nextpoint] == false) {
				q.push(nextpoint);
				check[nextpoint] = true;
			}
		}
	}
}

djm03178 6년 전 1

워낙 작은 수라 괜찮을 것 같긴 한데, 찜찜하면 double 쓰지 말고 제곱 상태로 비교해보세요.

그보다 하나 잘못된 건, resetArr을 n-1로 호출하시면 안 되죠. 이보다 작은 수까지 초기화하니까, n-1까지 초기화하려면 n으로 호출해야죠.

qwq713 6년 전 0

djm03178님 같은말 반복하시게해서 정말 죄송합니다. 경계값을 자꾸 고치다보니.. 결국 경계값 문제였네요

원래 코드 재활용을 아에 안하는데 너무 피곤해서 잠깐 편하려고 확인도안하고 저번꺼 코드 가져다 써서 결국 이렇게 되었네요 ㅠ

저번에 BFS 중복해결문제에 이어 다시한번 감사드립니다 !!!

아래는 완성된 코드입니다 감사합니다!!

#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#include<algorithm>
using namespace std;

typedef struct enemy {
	int y;
	int x;
	int radius;
}enemy;

void resetArr(bool * check, int n);			//check초기화해주는함수
double cal_distance(enemy e1, enemy e2);	//두 적 간의 거리 계산해주는 함수
bool is_connected(enemy e1, enemy e2);	//두 적이 연결되어있는지 확인해주는 함수
void bfs(int point);						//bfs 탐색 알고리즘 함수.

vector<int> list[3000];
bool check[3000];

int main(void) {
	ios_base::sync_with_stdio(false);
	int T;
	cin >> T;
		while (T--) {
			int cnt = 1;
			int N;
			cin >> N;
			vector<enemy> enemies;
			for (int i = 0; i < N; i++) {
				int tempX;
				int tempY;
				int tempR;
				cin >> tempX >> tempY >> tempR;
				enemy temp_enermy = { tempY,tempX,tempR };
				enemies.push_back(temp_enermy);
			}
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (i != j) {
						if (is_connected(enemies[i], enemies[j])) { //연결되어있으면 linked_list형식으로 추가해줌.
							list[i].push_back(j);
							list[j].push_back(i);
						}
					}
				}
			}
			for (int i = 0; i < N; i++) {
				if (check[i] == false) { //bfs시작된 횟수만큼 그룹의 수가 존재.
					bfs(i);
					cnt++;
				}
			}
			for (int i = 0; i < N; i++) { 
				list[i].clear();
			}
			//reset vector.

			resetArr(check, N);
			//reset checkArr
		cout << cnt - 1 << endl;
	}
	return 0;
}

double cal_distance(enemy e1, enemy e2) {
	double distance = sqrt((e1.x - e2.x)*(e1.x - e2.x) + (e1.y - e2.y)*(e1.y - e2.y));
	return distance;
}
bool is_connected(enemy e1, enemy e2) {
	double sumRadius = e1.radius + e2.radius;
	if (sumRadius >= cal_distance(e1, e2)) {
		return true;
	}
	else {
		return false;
	}
}

void resetArr(bool * check, int n) {
	for (int i = 0; i < n; i++) {
		check[i] = false;
	}
}

void bfs(int point) {
	queue<int> q;
	q.push(point);
	check[point] = true;

	while (!q.empty()) {
		int now = q.front();
		q.pop();
		for (int i = 0; i < list[now].size(); i++) {
			int nextpoint = list[now][i];
			if (check[nextpoint] == false) {
				q.push(nextpoint);
				check[nextpoint] = true;
			}
		}
	}
}

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

문제

문제

출처

ICPC

도저히 어디가 틀린지 모르겠네요...주석있어요!!

qwq713 6년 전 0

djm03178 6년 전 1

qwq713 6년 전 0

qwq713 6년 전 0

djm03178 6년 전 1

djm03178 6년 전 1

qwq713 6년 전 0

djm03178 6년 전 1

qwq713 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말