🥸 문제분석
1430 공격 문제와 굉장히 비슷하다고 느꼈던 문제.
치킨은 초당 v미터를 움직일 수 있고,
출발지점은 (xs, ys), 도착지점은 (xt, yt)이다.
그리고 m분 안에 벙커에 들어가지 않으면 순살 치킨이 된다.
즉, 치킨은 벙커에 들어가기 전까지 v*m*60 미터 미만까지 움직일 수 있다.
☝️ 문제풀이
이 문제에서 거슬리는 것은 벙커의 위치에 소수점이 가능해 실수 범위 좌표가 입력된다는 것이다.
심지어 v, m이 정수인지 실수인지도 언급하지 않고 있다.
그래서 일단은 모든 입력값이 실수가 될 수도 있다고 생각하고 코드를 작성한다.
v, m = map(float, input().split())
xs, ys = map(float, input().split())
xt, yt = map(float, input().split())그리고 벙커의 최대 개수는 1000개이고, 몇개가 입력될 지 알려주지 않기에 EOFError를 잡아내도록 코드를 작성해야 한다.
bunkers = set()
while True:
try:
temp = input()
if not temp: # 빈 문자열 체크
break
x, y = map(float, temp.split())
bunkers.add((x, y))
except:
break입력받은 문자열을 float으로 맵핑하고 튜플로 묶어 bunkers라는 이름을 가진 set에 담는다.
만약 정수 범위였다면 벙커의 위치를 2차원 배열에 기록할 수도 있었겠지만
실수 범위의 위치가 입력되기 때문에 어쩔 수 없이 집합에 저장하였다.
필자는 본 문제를 Kotlin으로도 제출했는데, 입력받은 문자열이 빈 문자열인 경우도 체크해야 Exception 없이 정상적으로 채점되었다. 파이썬도 그럴 것 같아 위 코드에서도 입력된 문자열이 빈 문자열인지 확인하였다.
이제 입력은 다 받았으니 문제를 어떻게 풀지 생각해보자.
치킨은 (xs, ys) 좌표에서 시작하여 매번 v*m*60 미터 미만까지 움직일 수 있다.
즉, 치킨은 자신의 위치를 중심으로 하면서
v*m*60 미터를 반지름으로 갖는 원의 면적만큼 움직일 수 있는 것이다.
위 그림은 치킨이 (xs, ys)에 위치하고 있을 때의 상황이다.
벙커가 여러곳에 있고, 치킨은 원의 면적 내에 들어오는 벙커로 이동하면 된다.
원의 면적에 들어왔다는 것은 어떻게 확인해야 할까?
더 좋은 방법이 있을 것 같지만, 필자는 평면에서 좌표 간의 거리를 구하는 식을 활용하였다.
calc_dist = lambda x, y, a, b: ((x-a)**2 + (y-b)**2)**0.5현재 위치와 벙커 사이의 거리를 구하고, 그 거리가 v*m*60 미만이라면 원 안에 들어오는 벙커라고 할 수 있다.
step_range = v * m * 60
visited = set()
q = deque([(xs, ys, 0)])
while q:
x, y, cnt = q.popleft()
if calc_dist(x, y, xt, yt) < step_range:
print(f'Yes, visiting {cnt} other holes.')
sys.exit()
for bunker in bunkers:
bx, by = bunker
if bunker not in visited and calc_dist(x, y, bx, by) < step_range:
visited.add(bunker)
q.append((bx, by, cnt + 1))
print('No.')방문처리 또한 set에 기록하였다.
벙커로 이동할 때마다 벙커 수를 카운트 하고,
이동하던 도중 도착지가 원의 면적 내에 들어오면 진행을 멈추면 된다.
목적지에 도착하면 BFS를 더이상 진행할 필요 없으므로 바로 sys.exit()으로 코드를 종료.
종료되지 않고 while문을 벗어나면 No. 를 출력하게 된다.
