글 읽기 - [C#] Union-Find 시간 초과 이유를 모르겠습니다.

paraworld 3년 전 0

원 위치 관계 구하면서 Sqrt()나 Pow()는 쓰지 않았고, Path Compression과 Union by Rank 둘다 적용한 것 같은데, 시간 초과랍니다.

뭔가 구현을 잘못했거나 제가 잘못 이해한 부분이 있는 것 같은데, 몇번을 봐도 어디가 문제인지 모르겠습니다.

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;

// CapitalLetters for class names and methods, camelCase for variable names.
// Write your code clearly enough so that it doesn't need to be commented, or at least, so that it rarely needs to be commented.

namespace Testpad
{
    public class BaekJoon10216
    {
        static int[] nodes;

        static void Main()
        {
            StreamReader sr = new StreamReader(Console.OpenStandardInput());
            StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

            int t = int.Parse(sr.ReadLine()); // TC의 수
            for (int i = 0; i < t; i++)
            {
                int n = int.Parse(sr.ReadLine()); // 거점의 수
                nodes = new int[n];
                List<(int x, int y, int r)> list = new List<(int x, int y, int r)>();

                for (int j = 0; j < n; j++) // 거점들을 받음
                {
                    int[] inputs = sr.ReadLine().Split().Select(int.Parse).ToArray();
                    int x = inputs[0], y = inputs[1], r = inputs[2];

                    list.Add((x, y, r));
                    nodes[j] = -1;
                }

                int result = n; // 집합의 수
                for (int j = 0; j < n; j++)
                {
                    for (int k = j + 1; k < n; k++)
                    {
                        if (Find(j) != Find(k))
                        {
                            // 두 지점 사이의 거리
                            int temp1 = list[j].x - list[k].x;
                            int temp2 = list[j].y - list[k].y;
                            int distance = temp1 * temp1 + temp2 * temp2;

                            if (distance <= (list[j].r + list[k].r) * (list[j].r + list[k].r))
                            {
                                Union(j, k);
                                result--;
                            }
                        }
                    }
                }

                // 결과 출력
                sw.WriteLine(result);
            }

            sr.Close();
            sw.Close();
        }

        static void Union(int a, int b)
        {
            a = Find(a);
            b = Find(b);

            if (a == b)
            {
                return;
            }

            // Union by Rank
            if (nodes[a] < nodes[b])
            {
                nodes[a] += nodes[b];
                nodes[b] = a;
            }
            else
            {
                nodes[b] += nodes[a];
                nodes[a] = b;
            }
        }

        static int Find(int a)
        {
            if (nodes[a] < 0)
            {
                return a;
            }
            else
            {
                // Path Compression
                nodes[a] = Find(nodes[a]);
                return nodes[a];
            }
        }
    }
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[C#] Union-Find 시간 초과 이유를 모르겠습니다.

paraworld 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말