[백준] 단계별로 풀어보기(단계:13, 기하1,JAVA)1004번, 어린 왕자

문제 링크

1004번: 어린 왕자

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심은

1. 출발점에서 도착점까지 행성계 진입/이탈의 최소 횟수를 결과로 출력합니다.

2. 경계에 맞닿거나 교차하는 경우가 없으며 경계에 출발점이나 도착점이 존재하지 않는다.

 

출발점에서 도착점까지 가는 거리는 신경쓰지 않기 때문에 행성계에 거리만 생각하고 알고리즘을 작성하면 됩니다.

 

행성계 경계에 진입/이탈을 하는 경우는 출발점이나 도착점 중 하나가 하나의 행성계에 안에 있고 밖에 있다면 경계를 지나야 합니다.

 

행성계 안에 있는 것을 확인하기 위해 행성계 중심에서 출발점이나 도착점에 거리가 반지름보다 작으면 안에 존재한다고 판단할 수 있습니다.

 

두 점사이의 거리를 구하는 공식은

거리 = ((x1 - x2)² + (y1-y2)²)의 제곱근

 

행성계 안에 출발점이나 도착점이 하나가 존재한다는 것을 확인하기 위해서

 

행성계 중심에서 출발점과 도착점에 거리를 구해서 둘 중 1개가 반지름보다 작으면 경계를 한 번 진입/이탈을 진행한다.

 

둘 중 1개가 되는지 확인하기 위해 XOR연산을 사용하여 확인하였습니다.

 

입력되는 모든 행성계에 관하여 출발점과 도착점을 탐색한 뒤 진입/이탈한 개수를 결과로 출력하면 됩니다.

 

 

문제를 해결한 알고리즘의 과정입니다.

1. 입력값을 저장합니다.

2. 각 행성계에 대하여 출발점과 도착점에 거리를 계산합니다.

3. 출발점과 도착점 중 하나만 행성계 안에 존재한다면 진입/이탈을 진행합니다.

4. 모든 행성계 탐색 후 진입/이탈을 한 횟수를 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer을 통해서 행성계 정보와 도착점, 출발점을 분리하였습니다.
• 행성계 중심에서 도착점과 출발점의 거리를 구합니다.
• 도착점과 출발점 중 하나만 행성계 안에 존재하면 진입/이탈을 진행합니다.
• 테스트 케이스마다 진입/이탈한 개수를 BufferedWrtier에 저장합니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

 

import java.util.*;
import java.io.*;
public class Main {
	static int T;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        	//입력값 처리하는 BufferedReader
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        	//결과값 출력하는 BufferedWriter
		StringTokenizer st;
		T = Integer.parseInt(br.readLine());
		for(int i=0;i<T;i++) {
			int result = 0;
            		//도착점, 출발점 저장
			st = new StringTokenizer(br.readLine()," ");
			int x1 = Integer.parseInt(st.nextToken());
			int y1 = Integer.parseInt(st.nextToken());
			int x2 = Integer.parseInt(st.nextToken());
			int y2 = Integer.parseInt(st.nextToken());
			int n = Integer.parseInt(br.readLine());
			for(int j=0;j<n;j++) {
                    		//행성계 정보 저장
				st = new StringTokenizer(br.readLine()," ");
				int cx = Integer.parseInt(st.nextToken());
				int cy = Integer.parseInt(st.nextToken());
				int r = Integer.parseInt(st.nextToken());
                		//행성계 중점에서 도착점과 출발점 거리 계산
				int startDistance = (int)Math.sqrt(Math.pow(x1-cx, 2) + Math.pow(y1-cy, 2));
				int endDistance = (int)Math.sqrt(Math.pow(x2-cx, 2) + Math.pow(y2-cy, 2));
				if(startDistance<r ^ endDistance<r)	//둘 중 하나만 행성계 안에 존재시
					result++;	//진입/이탈 발생
			}
			bw.write(result + "\n");		//해당 테스트케이스 결과 BufferedWriter 저장
		}
		bw.flush();		//결과 출력
		bw.close();
		br.close();
	}
}