[구현] 백준 1004번 (C++)

1004번: 어린 왕자

 

문제가 뭐야?

어린왕자가 출발점에서 도착점까지 가는데 행성을 최소 몇번 진입하고 탈출해야 하는지 구하는 문제

 

 

어떻게 풀꺼야?

출발점, 도착점 그리고 행성 사이의 관계를 생각해보면

• 행성 안에 출발점, 도착점 둘 다 존재
• 행성 안에 출발점, 도착점 둘 다 안 존재
• 행성 안에 출발점만 존재
• 행성 안에 도착점만 존재

근데 여기서 행성 안에 출발점, 도착점이 둘 다 존재하거나 or 둘 다 안 존재하면 해당 행성은 진입 및 탈출을 할 필요가 없다. 행성들 중 출발점이든 도착점이든 둘 중 1개만 존재하는 행성에서만 진입(탈출)하면 된다.

 

 

풀어보자

main함수에서 입력을 받고 모든 테스트 케이스에 대한 답을 출력한다

int main() {
    	//TESTCASES ANSWER
	vector<int> answer;

	//INPUT - TESTCASE
	int tc;
	cin >> tc;

	for(int i=0; i<tc; i++) {

		pair<int,int> start, end;
		vector<Circle> circles;

        	// INPUT - START POINT, END POINT
		int x1,y1,x2,y2;
		cin >> x1 >> y1 >> x2 >> y2;
		start = make_pair(x1,y1);
		end = make_pair(x2,y2);

		// INPUT - PLANET COUNT
		int cn;
		cin >> cn;

		// INPUT - PLANET
		for(int j=0; j<cn; j++) {
			int x,y,r;
			cin >> x >> y >> r;

			Circle c;
			c.setCircle(x,y,r);

			circles.push_back(c);
		}

		// TESTCASE'S SOLVE
		int ans = solve(circles,start,end,cn);
		answer.push_back(ans);
	}

	// OUTPUT - TESTCASES ANSWER
	for(int ans:answer) cout << ans << endl;
	return 0;
}

 

solve함수에서 각 테스트 케이스의 최소 진입 및 탈출 횟수를 계산한다

// FIND PLANET WHICH HAS ONLY ONE POINT
int solve(vector<Circle> &circles, pair<int,int> start, pair<int,int> end, int cn) {
	//PLANETS, START POINT, END POINT, PLANET COUNT

	int answer = 0;

	for(int i=0; i<cn; i++) {
		//START POINT IN CHECK
		if(distance(circles[i].x,circles[i].y,start.first,start.second) <= circles[i].r) {
			circles[i].in_point++;
		}
		//END POINT IN CHECK
		if(distance(circles[i].x,circles[i].y,end.first,end.second) <= circles[i].r) {
			circles[i].in_point++;
		}
	}

    	// UPDATE ENTER(ESCAPE) COUNT
	for(int i=0; i<cn; i++){
		if(circles[i].in_point == 1) answer++;
	}

	return answer;
}

 

행성안에 출발점(도착점)이 존재하는지 확인하기 위해 행성의 중심점과 출발점(도착점) 사이의 거리를 구해서 행성의 반지름과 비교했다

// GET DISTANCE BETWEEN POINT1 AND POINT2
float distance(int px1, int py1, int px2, int py2) {
	return sqrt(pow(px1-px2,2)+pow(py1-py2,2));
}

 

각 행성을 (중심 좌표, 반지름, 내부에 점이 몇 개 있는지) 클래스로 표현했다

// PLANET CLASS
class Circle {
	public:
		int x;
		int y;
		int r;
		int in_point;

		void setCircle(int _x,int _y, int _r) {
			x = _x;
			y = _y;
			r = _r;
			in_point = 0;
		}
};