자료구조 과제 투캅스

저희 교수님은 알고리즘으로 저명하신 분이셔서 자료구조와 알고리즘 수업의 끝판왕이라고 불리십니다. 

핵심은 과제의 수와 비율인데요.

한 학기에 약 20개 정도로 쏟아지는 과제를 감당해야합니다. 

 

이번 과제는 투캅스라는 과제로 그래프의 꼭짓점이 주어지고 그래프를 따라 항상 1씩 이동하는 두 로봇의 최종 위치를 결정하는 거였습니다. 로봇은 처음에 마주 보는 방향으로 움직이고 부딪힐 경우 반대 방향으로 이동합니다. 

 

어려웠던 점은 홀수 거리, 짝수 거리가 남았을때의 처리 방법이었는데요. 

제가 과제를 잘 이해하지 못해서 헤맸던 거 같습니다. 

처리 방식은 다음과 같습니다. 

 

 

이 부분은 이해하기 쉬웠습니다. 

제가 헷갈렸던 점은 이부분인데요. 교수님이 말씀해주시길 로봇은 항상 '1' 만큼 이동하기 때문에 0.5초사이에 0.5 만큼 갔다가 나머지 0.5초 후에 0.5 를 더 가서 제자리로 돌아오는 겁니다!

 

또 한가지는 부딪히는 지점 계산인데요. 

처음에는 초마다 반복문으로 계산을 했더니 시간초과가 뜨더라구요.

좀 더 로봇이 만나는 위치를 여러번 살펴보면 항상 똑같은 두 곳에서 만나는 것을 알 수가 있습니다. 

 

 

다음과 같은 느낌으로 계속 만나게 되기 때문입니다. 

전체코드는 저의 깃허브에 가사면 예제와 함께 보실 수 있습니다. 

 

github.com/Chung-god/DataStructureHW/blob/master/HW2_twocop/twocop.cpp

Chung-god/DataStructureHW