문제
어린 왕자는 소혹성 B-664에서 자신이 사랑하는 한 송이 장미를 위해 살아간다. 어느 날 장미가 위험에 빠지게 된 것을 알게 된 어린 왕자는, 장미를 구하기 위해 은하수를 따라 긴 여행을 하기 시작했다. 하지만 어린 왕자의 우주선은 그렇게 좋지 않아서 행성계 간의 이동을 최대한 피해서 여행해야 한다. 아래의 그림은 어린 왕자가 펼쳐본 은하수 지도의 일부이다.
빨간 실선은 어린 왕자가 출발점에서 도착점까지 도달하는데 있어서 필요한 행성계 진입/이탈 횟수를 최소화하는 경로이며, 원은 행성계의 경계를 의미한다. 이러한 경로는 여러 개 존재할 수 있지만 적어도 3번의 행성계 진입/이탈이 필요하다는 것을 알 수 있다.
위와 같은 은하수 지도, 출발점, 도착점이 주어졌을 때 어린 왕자에게 필요한 최소의 행성계 진입/이탈 횟수를 구하는 프로그램을 작성해 보자. 행성계의 경계가 맞닿거나 서로 교차하는 경우는 없다. 또한, 출발점이나 도착점이 행성계 경계에 걸쳐진 경우 역시 입력으로 주어지지 않는다.
입력
입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 첫째 줄에 출발점 (x1, y1)과 도착점 (x2, y2)이 주어진다. 두 번째 줄에는 행성계의 개수 n이 주어지며, 세 번째 줄부터 n줄에 걸쳐 행성계의 중점과 반지름 (cx, cy, r)이 주어진다.
출력
각 테스트 케이스에 대해 어린 왕자가 거쳐야 할 최소의 행성계 진입/이탈 횟수를 출력한다.
제한
- 1000 ≤ x, y, x, y, c, c ≤ 1000 1 1 2 2 x y
- 1 ≤ r ≤ 1000
- 1 ≤ n ≤ 50
- 좌표와 반지름은 모두 정수
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
T = int(input())
for i in range(T):
count = 0
# 출발지와 도착지
x1,y1,x2,y2 = map(int,input().split())
# 행성계의 개수
N = int(input())
# 중점 좌표와 반지름
for j in range(N):
cx,cy,r = map(int,input().split())
dist_1 = (x1 - cx)**2 + (y1-cy)**2
dist_2 = (x2 - cx)**2 + (y2-cy)**2
r_squared = r**2
if dist_1<r**2 and dist_2<r**2:
continue
elif r_squared > dist_1 or r_squared > dist_2:
count +=1
print(count)
완전히 틀렸던 접근방식 BFS
출력: 각 테스트 케이스에 대해 어린 왕자가 거쳐야 할 최소의 행성계 진입/이탈 횟수를 출력한다.
예상 알고리즘: BFS
이유: 여러 경로를 살펴보아야 하고, 그 중에서 최단 거리는 아니어도, 최소의 진입/이탈 횟수를 구하는 것이기 때문
응용: 기존에 최단거리를 구하려고 할 때, 이전 좌표의 value 값을 다음 좌표의 value값을 더해주었었다.
이번에는 거리가 아니라, 진입/이탈 횟수를 count 해야 되기 때문에, 원 안의 좌표들을 구해놓고 해당 좌표에 진입/이탈 시에만 count를 1 더해준다.
구현 방안:
- 중점의 위치와 반지름을 이용해서, 해당 원 안에 포함되는 좌표들을 구한다.
- BFS로 Loop을 돌면서, 다음 nx,ny가 해당 좌표 안에 포함되게 되면 count를 1 더한다.
- 마지막에 종점 좌표의 값을 반환해준다.
위의 BFS를 활용한 접근방식이 틀린 이유는 문제에서 ‘거리‘에 대한 요구사항이 없기 때문에 마음만 먹으면 얼마든지 돌아서라도 행성계를 피해서 운전할 수 있다.
따라서, ‘불가피하게’ 행성계를 거칠 수 밖에 없는 케이스만 고려하면 된다.
수학, 구현을 활용한 접근 방식
불가피한 케이스:
BOTH 출발지와 도착지가 동일한 행성계 안에 있을 때:
- 진입 및 이탈 횟수: 0
ONLY the START 출발지만 N개의 행성계 안에 있을 때:
- 이탈 횟수: N
ONLY the END 도착지만 N개의 행성계 안에 있을 때
- 진입 횟수: N
BOTH BUT SEPARATE 출발지는 N개의 행성계 안에, 도착지는 M개의 행성계 안에 있을 때
- 진입 및 이탈 횟수: N+M
따라서 행성계의 좌표 정보를 받아서, 출발지와 도착지가 해당 좌표들에 포함되는지, 만약 포함된다면 몇 개에 포함되는지만 확인하면 된다.
위에서 진입 이탈 횟수를 N과 M으로 표기하기는 했지만, 루프를 돌면서 행성계를 하나씩 살펴볼것이기 때문에, 그냥 포함된다면 count를 1 더해주고 아니라면 continue하면 된다.
특정 좌표가 행성계 안에 있는지 판단하는 법:
- x1,y1 혹은 x2,y2로부터 r간의 거리 < r과 cx,cy간의 거리
출발지/도착지 좌표가 동일한 행성계 안에 있는지 판단하는 법:
- x1,y1로부터 r간의 거리 < r과 cx,cy간의 거리 and x2,y2로부터 r간의 거리 < r과 cx,cy간의 거리
점과 점 사이의 거리를 구하는 공식 (from (x1,y1) to (y1,y2))
(x2 - x1)2 + (y2-y1)2
원래 위에 루트를 씌워야 하지만, 비교하는 대상인 반지름(r)에 대신 제곱해서 비교