|
S.W Expert. 6057그래프의 삼각형(D3) |
|
|
이전코드(2000ms 초과) |
이후코드(411ms) |
|
for t in range(int(input())): tri=0 N,M = tuple(map(int,input().split())) L=[[] for i in range(N-1)] pair=[] for m in range(M): a,b= list(map(int,input().split())) pair.append({a,b}) L[a-1].append(b) for n in range(N-2): for i in range(len(L[n])): for j in range(i+1,len(L[n])): if {L[n][i],L[n][j]} in pair: tri+=1 print(f"#{t+1} {tri}")
|
for t in range(int(input())): tri=0 N,M = map(int,input().split()) L=[[] for i in range(N-1)] pair=[] for m in range(M): a,b= map(int,input().split()) L[a-1].append(b) for n in range(N-2): for i in range(len(L[n])): for j in range(i+1,len(L[n])): a=L[n][i] b=L[n][j] if ( (a < b) and (b in L[a-1]) ) : tri+=1 elif ((a > b) and (a in L[b-1]) ) : tri+=1 print(f"#{t+1} {tri}")
|
|
2차원 배열 L에 i정점과 연결된 모든 정점을 L[i]의 리스트에 저장했다. Ex) [[2,4],[3,4],[4]] 정점1과 연결된 점은 2,4 , 정점2와 연결된 점은 3,4 , 정점3과 연결된 점. 삼각형이 되는지 확인하기 위해선 L[i]속의 값들을 두개씩 짝지은 뒤 그 두개의 점이 이어져 있는지 확인하는 방법을 이용하면 된다. 이때 수정 전 코드는 입력되는 값들을 따로 pair라는 리스트에 저장해서 그 두개의 점이 존재 하는지 확인하는 방법을 이용하였고 수정 후 코드는 만들어진 L리스트에 L[i]만 서치하는 방법을 사용하였다. pair라는 리스트는 모든 간선들이 존재하는 리스트로써 한쌍의 점을 확인하고자 할 때마다 전체를 다(M번) search해야 하였지만, L[i]만 서치하는 방법을 이용한다면 i와 연결되있는 정점 중 i보다 큰 점들에 대해서만 조사하면 되기 때문에 실행속도를 많이 줄일 수 있다. |
|