글 읽기 - 파이썬 시간초과 질문드립니다 ..

hsw0194 3년 전 0

nodes안에 각 무선기지?를 넣어주고

N개의 node들끼리 겹치나 안겹치나 체크해서

서로 겹친다고 판단하면

노드를 이어주었습니다 (양방향)

그후 0번부터

bfs 탐색실시해서

총 몇개의 뭉치는게 생기는지

카운트하는데 시간초과가 나네요..

어디부분이 문제일까요?

from sys import stdin
from collections import deque

dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]


class node:
  def __init__(self, pos_x, pos_y, r):
    self.posx = pos_x
    self.posy = pos_y
    self.r = r


def bfs(i):
  q = deque()
  q.append((i))

  while q:
    src = q.popleft()

    for dest in range(N):
      if not visited[dest] and connection[src][dest]:
        q.append((dest))
        visited[dest] = True


T = int(stdin.readline())
visited = [[]]

while T:
  N = int(stdin.readline())
  visited = [False for _ in range(N + 1)]
  connection = [[False] * N for _ in range(N)]
  nodes = []
  for _ in range(N):
    pos_x, pos_y, r_value = map(int, stdin.readline().split())

    nodes.append(node(pos_x, pos_y, r_value))

    # start_x = 0
    # start_y = 0

    # end_x = 0
    # end_y = 0

    # if pos_x - r_value < 0:
    #   start_x = 0
    # else:
    #   start_x = pos_x - r_value

    # if pos_x + r_value > 4999:
    #   end_x = 4999
    # else:
    #   end_x = pos_x + r_value

    # if pos_y - r_value < 0:
    #   start_y = 0
    # else:
    #   start_y = pos_y - r_value

    # if pos_y + r_value > 4999:
    #   end_y = 4999
    # else:
    #   end_y = pos_y + r_value

    # start_x = (pos_x - r_value < 0 and 0 or pos_x-r_value)
    # end_x = (pos_x + r_value - 1 > 4999 and 4999 or pos_x + r_value - 1)

    # start_y = pos_y - r_value < 0 and 0 or pos_y - r_value
    # end_y = pos_y + r_value - 1 > 4999 and 4999 or pos_y + r_value - 1

    # for i in range(start_y, end_y + 1):
    # for j in range(start_x, end_x + 1):
    # grid[i][j] = True
  for i in range(N):
    for j in range(N):
      if i == j: continue

      diff_x = nodes[i].posx - nodes[j].posx
      diff_y = nodes[i].posy - nodes[j].posy
      sum_r = nodes[i].r + nodes[j].r

      if (diff_x * diff_x + diff_y * diff_y) <= (sum_r * sum_r):
        connection[i][j] = connection[j][i] = True

  cnt = 0

  for i in range(N):
    if not visited[i]:
      visited[i] = True
      bfs(i)
      cnt += 1

  print(cnt)

  T -= 1

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

문제

문제

출처

ICPC

파이썬 시간초과 질문드립니다 ..

hsw0194 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말