백준 1004 : 어린 왕자 - C# 풀이

일단, 이 문제는 문제를 이해하는 것이 가장 어려웠다. 이해만 한다면 생각보다 쉽게 풀 수 있을 것이다.

문제 사진

 

일단 문제를 간소화해 보면, "원의 교점"을 찾는 문제이다.

항성계는 경계가 있어서 진입/이탈을 판별할 수 있는데, 이때 원의 교점과 진입/이탈의 수가 같다.

또한 여기서 한 가지 조건이 더 있는데 "최소"라는 것이다. 나는 이걸 제대로 이해 못 해서 오래 걸렸는데,

피할 수 있으면 피한다는 뜻이다. 피할 수 있는 진입/이탈은 문제 사진처럼 시작점과 도착점 사이에

원이 있어서 곡선으로 가는 상황이 있다.

 

따라서 이 문제를 최대한 요약하면 다음과 같다. 

-> 시작점과 끝점을 곡선으로 잇는 과정에서 피할 수 없는 원과의 접점을 구하라.

풀어보자.

---

1. 입력의 구조 파악하기, 알고리즘 설계

입력의 예시

일단 처음에는 테스트할 케이스의 개수가 주어진다. 서로 다른 2번의 경우를 테스트한다는 것.

다음 줄은 시작점과 끝 점이 주어진다. 시작점(-5, 1)과 끝점(12, 1)이 주어진 꼴이다.

 

그다음은 항성의 개수를 준다. 총 7개의 항성계를 고려해야 함을 알 수 있다.

그 후로는 7가지 항성의 x, y, r (좌표와 반지름)이 주어진다.

 

7개의 좌표와 반지름이 다 출력되면 2번째 케이스로 넘어가며

다시 항성의 개수 (1), 항성의 좌표와 반지름이 주어지는 걸 볼 수 있다.

 

알고리즘 설계)

일단 기본적인 이론은 각 항성계마다 따로따로 접점이 생기는지 확인한다.

이때 줄마다 주어진 정보가 다르기에 줄의 번호에 주의해야 한다.

 

2라는 케이스 개수를 받으면 2번 반복하고, 그다음 줄인 시작점과 끝점은

변수로 저장해 놓으며, 항성의 개수인 7이 나오면 7번 반복하여

각 항성마다 원의 접점을 고려하면 된다.

 

7번 반복이 끝나면 상위 반복문(총 2번 반복하는)이 두 번째로 반복되며

다음 케이스로 넘어가게 된다. 이 이론을 기본으로 설계를 시작하자.

---

2. 코드와 설명

using System;

namespace unicoti {
    class Program {
        static void Main(string[] args) {
            string input = Console.ReadLine();
            int repeat = int.Parse(input);

            for (int i = 0; i < repeat; i++) {
                string[] Outinputs = Console.ReadLine().Split(' ');
                int x1 = int.Parse(Outinputs[0]);
                int y1 = int.Parse(Outinputs[1]);
                int x2 = int.Parse(Outinputs[2]);
                int y2 = int.Parse(Outinputs[3]);

                int caseCount = int.Parse(Console.ReadLine());
                int count = 0;

                for (int j = 0; j < caseCount; j++) {
                    string[] Ininputs = Console.ReadLine().Split(' ');
                    int cx = int.Parse(Ininputs[0]);
                    int cy = int.Parse(Ininputs[1]);
                    int r = int.Parse(Ininputs[2]);

                    bool startInside = IsInsideCircle(x1, y1, cx, cy, r);
                    bool endInside = IsInsideCircle(x2, y2, cx, cy, r);

                    if (startInside != endInside) {
                        count++;
                    }
                }

                Console.WriteLine(count);
            }
        }

        static bool IsInsideCircle(int x, int y, int cx, int cy, int r) {
            int dx = x - cx;
            int dy = y - cy;
            return dx * dx + dy * dy < r * r;
        }
    }
}

 

(예시 입력 1로 설명)

나는 이렇게 설계했다. 물론 겹치는 부분도 많아서 리팩터링 할 부분이 충분히 보이지만

당장은 알고리즘 설계에 의미를 두고 풀고 있는 만큼 넘어가겠다.

 

일단 처음 줄에서 케이스의 개수를 알려주므로

저장하여 repeat라는 변수에 저장한다. 몇 번 반복할지 저장한 것이다.

이후 for문으로 repeat만큼 반복하도록 설정했다. (2회 반복)

 

2번 반복하는 대상이 "케이스"인데, 형식이 시작점과 끝점을 알려주고

몇 번 반복할지 알려주며 항성의 정보를 알려주기에

for내부로 들어가서 가장 먼저 시작점과 끝점을 입력받아 저장했다.

x1, y1, x2, y2라는 변수로 저장해 주었다.

 

이후 다음줄은 항성의 개수를 담고 있기에 caseCount에다가 항성의 개수를 저장했다.

이제 항성마다 접점을 구할 것이기에 for문으로 한 줄씩, 항성마다 정보를 읽어주었다.

cx, cy, r로써 그 정보들을 저장했다.

 

이때 아이디어가 들어간다. 접점을 피할 수 없는 경우를 일반화하면 어떤 것일까?

항성 내부에 시작점이나 끝점이 있는 경우이다. 이건 원 안에 점이 있기에

어떤 곡선으로도 원을 벗어나려면 1개의 접점이 필요하다.

 

이걸 빠르게 판단하기 위해서 함수를 만들었다. x, y, cx, cy, r을 넣으면

점이 원 안에 있는지를 bool값으로 판단해 주는 함수이다.

 

마지막으로 코드 후반부의 if문인데, 한 원에서 저 bool값이 다르면

카운트를 올려주었다. 한 원 안에 두 점이 있거나 두 점 사이에 만나지 않는 원이 있다면

카운트가 증가하지 않기에 한 원이 둘 중 한 점만 내부에 지닌다면 카운트는 무조건 증가하게 된다.

이렇게 일반화를 해줘서 카운트를 늘리는 경우를 간단히 처리해 주었다.

 

for문의 끝부분에 출력을 진행하여 케이스마다 값을 출력하도록 설계했다.

이로써 백준이 원하는 답을 설계할 수 있었다.

---

오늘의 느낀 점)

문제 이해가 가장 중요하다고 느꼈다. 터렛 문제를 포함해서 너무 돌려서 말하는 것 같다.

이럴 거면 차라리 아예 수학적으로 말해줬으면 좋겠다. 또한 ai에게 질문도 하면서 했는데

ai도 푸는 법만 학습했지 문제를 완벽히 이해는 못하고 잘못된 답변을 계속하는 걸 볼 수 있었다.

1003번 때 느낀 대로 휴대폰으로 계속 문제 이해를 시도하고 있었는데 생각보다 어려웠다.

 

이런 것도 경험이라 생각하고, 수학 문제를 푸는데도 도움이 되는 것 같다.

또한 순수 C#도 꽤 익숙해지고 있어서 유니티에서 코드를 쓰는 것처럼 꽤나 자연스럽게

내 생각을 코드로 적고 있다. 내일도 문제를 풀어서 글로 남기길 바란다.

---

이상으로 도움이 되었길 바라며,

 

끝.