[BOJ][Python]1004 풀이

https://www.acmicpc.net/problem/1004

1004번: 어린 왕자

import sys

ssr = sys.stdin.readline

t = int(ssr())
for _ in range(t):
    points = list(map(int, ssr().split()))
    n = int(ssr())
    planets =[list(map(int, ssr().split())) for _ in range(n)]
    ans = 0
    for i in range(n):
        tmp = 0
        if ((points[0] - planets[i][0])**2 + (points[1] - planets[i][1])**2)**0.5 < planets[i][2]:
            tmp += 1
        if ((points[2] - planets[i][0])**2 + (points[3] - planets[i][1])**2)**0.5 < planets[i][2]:
            tmp += 1
        ans += tmp % 2
    print(ans)

이번 문제는 어렵진 않지만 기쁜 문제였습니다. 어제 자기 전에 풀어놓고 자려고 했는데 도통 방법이 생각이 안나서 저 스스로에게 약간 실망했었는데, 또 오늘 풀려고 하니까 금방 방법이 생각이 나더라구요. 당장 방법이 생각나지 않을 때는 다른 것부터 하거나 한 숨 자고 오는 것도 좋은 것 같습니다. 수없이 들은 말이고 몇 번 직접 경험도 했으면서 막상 조급할 때는 쉽게 놓지 못하는 건 버릇인가 봅니다.

 

저는 이 문제를 케이스 분류를 하면서 일반화할 수 있는 방법을 생각하다보니 풀이법이 생각났습니다.

1. 출발점과 도착점이 같은 행성의 경계(이하 '원') 안에 있는 경우

2. 출발점과 도착점이 같은 원 안에 있지 않은 경우

3. 출발점과 도착점이 같은 원 안에 있지 않지만, 그 바깥에 모두를 포함하는 원이 존재할 경우

0. 전제조건

- 출발점에서 도착점으로 가는 경로는 직선이 아니어도 상관없는 자유곡선입니다.

- 원과 원은 절대 접하지도 교차하지도 않습니다.

- 출발점과 도착점이 원의 위에 존재하는 경우는 없습니다.

1. 출발점과 도착점이 같은 원 안에 있는 경우

원끼리 접하거나 교차할 수 없고 출발점과 도착점도 원에 접하지 않기 때문에 출발점과 도착점이 너무 가까워서 같은 원 안에 있는 경우는 입력으로 아무리 많은 원이 나오더라도 무조건 0이 나올 것입니다. 그렇다면 하나의 반복문에서 원을 기준으로 출발점과 도착점의 위치를 판단(원의 중심과 좌표의 거리를 구하고 원의 반지름보다 작다면 원 안에 존재)하면 되겠네요. 조건문을 만들어서 0으로 처리해버리면 될까요? 일단은 다른 경우도 살펴봅시다.

2. 출발점과 도착점이 같은 원 안에 있지 않은 경우

출발점과 도착점으로 가는 경로는 직선이 아니어도 상관없기 때문에 출발점과 도착점이 원 안에 존재하지 않는 이상 결과는 0이 나옵니다. 즉, 출발점과 도착점이 원 안에 있는 경우를 체크하면 정답으로 이어지는 길이 나오겠다는 추론이 가능하죠. 원 마다 체크해서 기록한 다음에 최종적으로 합해서 출력하면 되겠네요.

3. 출발점과 도착점이 같은 원 안에 있지 않지만, 그 바깥에 모두를 포함하는 원이 존재할 경우

예를 들어 5개의 동심원이 있고 출발점은 작은 순서대로 1, 2, 3의 원 안에 있고, 도착점은 4, 5의 원 안에 있다고 해봅시다. 2번에서 처럼 원 안에 있는 경우를 체크해서 다 더한다면 출발점은 총 5개의 원 안에 있고 도착점은 2개의 원 안에 있으니 최종합은 7이 되죠. 하지만 이건 정답이 아니죠. 1, 2, 3의 원만 통과하면 도착점에 도착할 수 있으니 답은 3입니다. 그러면 빼줘야 하겠네요. 또 조건문을 쓰자니 비효율적인 것 같습니다.

일반화 과정

1번 경우와 3번 경우는 글로 보면 다르지만 핵심을 놓고 보면 출발점과 도착점이 같은 원 안에 존재할 때 올라갔던 카운트를 다시 낮춰주는 과정이 필요하다는 것인데 카운트가 1이면 빼고 0이면 더하는 식의 조건문으로 판단하는 것은 비효율적일 것이라는 생각이 들었습니다. 2번에서 나왔던 카운트해서 최종합을 구하는 것을 기본틀로 잡고 1, 3의 경우를 끼워 맞춰보고 싶은데요. 그러면 그냥 카운트를 한 다음에 2개면 0으로 만들면 코드 한 줄만 추가하면 기본틀을 벗어나지 않고 정답을 구하는 과정을 일반화할 수 있을 것 같은데요. 그렇다고 2이면 0으로 만드는 조건문을 넣는 것도 귀찮으니까 2의 나머지를 ans에 더해버리면 되겠습니다(2는 0이 되고 1은 1이 되므로).

 

이번에도 다른 분의 코드를 좀 살펴봤는데 알면 간단하면서도 괜찮은 조건문인 것 같아서 소개를 해보겠습니다. 아래는 다른 분의 로직을 제 코드에 맞게 바꾼 것입니다.

for i in range(n):
    if ((points[0] - planets[i][0])**2 + (points[1] - planets[i][1])**2 - planets[i][2]**2) *  ((points[2] - planets[i][0])**2 + (points[3] - planets[i][1])**2 - planets[i][2]**2) < 0:
        ans += 1

조건문이 너무 길어서 이게 뭔가 싶겠지만 이 조건문의 내용은 (원의 중심에서 출발점까지의 거리 - 원의 반지름) * (원의 중심에서 도착점까지의 거리 - 원의 반지름)이 음수라면 카운트하고 짝수이면 카운트를 하지 않는 것입니다. 바로 눈치채신 분들도 있을텐데 해당 조건이 0보다 큰 경우는 둘 다 음수(원의 반지름보다 작아서 원 안에 존재)이거나 둘 다 양수(원의 반지름보다 커서 원 밖에 존재)라는 뜻이 됩니다. 즉, 원을 통과할 필요가 없는 경우라는 뜻이 되고, 반대로 말하면 해당 조건이 0보다 작은 경우는 무조건 원을 통과하는 경우라는 뜻이 되는 것이죠.

 

제법 이런 류의 판단을 해봤던 기억들이 있으실 것 같습니다. 수학 문제에서 자주 볼 수 있죠. 알고 보면 간단한데 막상 시간 압박이 있는 시험같은 경우에 이 문제를 맞닥뜨렸다면 저는 이 정도까지 논리가 발전할 수 있었을까하는 자신이 들지 않네요. 무언가를 쉽게 하는 사람이 있다면 그 사람이 정말 잘하는 사람이라는 말이 괜히 받아들여지는게 아닌 것 같습니다.