백준 BOJ 파이썬 22948 원 이동하기2

22946 원 이동하기 1이랑 똑같이 하면 될 줄 알았다.

트리를 만든 후 특정 경로의 길이와 추적..

트리 만드는 코드는 그대로하고

바로 경로 길이와 추적하는 코드를 작성하였지만

실행 시간 초과.. 멘붕이었다.

원 이동하기 2, n의 갯수는 최대 20만개

원 이동하기 1, n의 갯수는 5천개

시간복잡도의 엄청난 차이가 있을 것이다.

원 이동하기2는 모든 원의 y 좌표를 0으로 고정해놨다.

일일이 두 원의 거리 공식을 계산하는 것이 아니라

괄호쌍 판별의 개념을 이용하여 트리를 만들어야한다.

여기서 최소힙의 개념을 이용해야한다.

이유는?

좌표평면의 가장 왼 쪽에 있는 x좌표부터 오른쪽 좌표까지 순서대로!

왼쪽부터 오른쪽까지 촤르르 비교하게끔

문제의 예시로 과정을 설명하자면

스택에 좌표평면인 0을 넣는다.

heap의 pop을 하면 1의 가장 왼쪽에 있는 좌표를 꺼낸다.

0과 1을 이어준다.(부모,자식 관계가 된다.)

그리고 스택에 1을 append한다.

그 다음 꺼내는 좌표는 2의 왼쪽 좌표

1(stack[-1])과 2를 이어준다.

stack에 2를 append

그 다음 나오는 좌표는 2의 오른쪽 좌표

스택에서 2를 제거한다.

1과 3이 이어주고, 3 스택에 쌓고

3 스택에서 제거하고, 1 스택에서 제거하고

0과 4이 이어주고, 4 스택에 쌓고

4스택에서 제거하고...

이런 식으로 트리를 만들어준다.

이것을 괄호쌍 판별이라 부르는 것 같다.

(참고로 원의 왼쪽은 +(원의 번호),오른쪽은 -(원의 번호로) 했다.

그래서 원의 번호가 0보다 작으면 오른쪽 좌표인 것이다.)

그 후, 경로 길이와 추적은 bfs,dfs 둘 다 해봤는데

실행시간은 큰 차이가 없는 것 같다.

편한대로 하면 될 것 같다.

 

import sys
from collections import deque
from itertools import combinations
import math
import heapq as hq
 
sys.setrecursionlimit(10000)
 
 
##a에서 b가는 경로와 방문한 원의 갯수 찾아주기
def atob(L,x):
    if x==b:
        print(L)
        for x in path:
            print(x,end=' ')
        #print()
        exit()
 
    for y in graph[x]:
        if ch[y]==-1:
            ch[y]=1
            path.append(y)
            atob(L+1,y)
            path.pop()
            ch[y]=-1
 
def backtrace(b):
 
    #print(b,end=' ')
    res.append(b)
    x=path[b] ##부모 노드 찾아가기
    if x!=-1:
        backtrace(x)
    
 
if __name__=='__main__':
    #sys.stdin=open("input2.txt", "rt")
 
    n=int(input())
    circle=[]
    #circle=[list(map(int,input().split())) for _ in range(n)] ##원의 정보 입력 받기 (원의 번호,원의 중심 x 좌표,반지름)
    for _ in range(n):
        num,x,r=map(int,input().split())
        circle.append((x-r,num))
        circle.append((x+r,-num))
    a,b=map(int,input().split()) ##출발점=a,도착점=b 정보 입력 받기
 
    #circle.sort(reverse=False,key=lambda x:x[2]) ## 원의 반지름이 큰 것부터 작은 것까지 내림 차순 정렬
    #circle.append[0,0,float('inf')] ##좌표평면 맨 앞에 투입
    ##트리 만들기
    graph=[[] for _ in range(n+1)]
   
    hq.heapify(circle) ## 서클의 정보 최소힙으로
 
    stack=[0]
    q=deque()
    while circle:
        x,num=hq.heappop(circle)
        if num<0: #원의 오른쪽 좌표면 원이 끝났으니 스택에서 제거해준다.
            stack.pop()
        else:
            graph[num].append(stack[-1])
            graph[stack[-1]].append(num)
            stack.append(num)
 
    #print(graph)
    dist=[-1]*(n+1)
    res=[]
    path=[-1]*(n+1)
 
    #q.append(a)
    #dist[a]=1
    ch=[-1]*(n+1)
    ch[a]=1
    path=[a]
    atob(1,a)