[문제출처 : Codechef] 세 사람이 각각 (x, y)의 2차원 평면에 위치해 있습니다. 세 사람은 무전기를 가지고 있는데, 이 무전기가 통신 가능한 거리가 R로 한정되어 있습니다. 이 때, Relay통신을 허용한다고 했을 때,(즉, 1번 사람이 3번 사람과 연락할 때, 2번을 통해서 할 수 있습니다.) 이 세 사람이 서로 무전을 주고 받을 수 있으면 True를, 아니면 False를 리턴하는 함수를 만들어 주세요.

일단 한 평면상에 ($x_1$, $y_1$), ($x_2$, $y_2$) 사이의 거리는 아래와 같이 구할 수 있습니다. \[D=\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}\]

어차피 $D=R$을 비교하는 것과 $D^2=R^2$을 비교하는 것이 등가이므로, 우리는 squared distance를 구하는 함수로 구현하겠습니다.(sqrt함수에 의해 running time이 조금이라도 영향을 받기 때문입니다.)

def getDistSq(pos1, pos2):
    return ((pos1[0]-pos2[0])**2 + (pos1[1]-pos2[1])**2)

>>> print getDistSq((0,0), (1,1))
2

함수의 결과가 잘 나옴을 확인할 수 있네요. 그렇다면 어떻게 하면 효율적으로 세 사람이 서로 간에 통신이 가능한지 파악할 수 있을까요? 결국 이 문제의 포인트는 서로간에 도달할 수 있는 최소한 한 가지 경로가 있는지를 묻는 문제와 같다고 보실 수 있습니다. 세 사람 간에 연결될 수 있는 총 가지 수는 \[{3 \choose 2}=3\] 가지인데요, 이 3가지 경우 중 2개 이상의 거리가 R보다 작거나 같으면 세 사람은 서로 연결되었다고 볼 수 있습니다.(설령 direct 통신은 불가능 해도, relay가 가능하다고 했기 때문입니다.) 해서 함수를 구현하면 아래와 같습니다.

def isCommPossible(positions, R):
    nRoute = 0
    for i in range(len(positions)-1):
        for j in range(i+1, len(positions)):
            sqDist = getDistSq(positions[i], positions[j])
            if sqDist <= R**2:
                nRoute += 1

    #연결 가능한 루트가 2개 이상이면 True를 리턴합니다.
    return nRoute >= 2

이제 결과가 잘 맞는지 확인해 보겠습니다.

>>> print isCommPossible([(0,1), (0,0), (1,0)], 1)
True
>>> print isCommPossible([(0,1), (0,0), (1,0)], 2)
True
>>> print isCommPossible([(0,0), (0,2), (2,1)], 2)
False