15591-Mootube(시간초과)

Mootube라는 문제를 읽고 이해하는데 오랜 시간이 걸렸다.

결론부터 말하자면 테스트케이스의 정답은 나오나 문제를 해결하는데 너무 많은 반복문과 while문 사용으로 인한 시간초과가 일어났다.

후에 정답을 확인한 결과 N X N 테이블을 만드는게 아닌 BFS로 해결하는 문제였다.

예전에도 DFS문제를 풀때 N X N테이블을 만들어서 풀이를 하니까 시간초과가 났었는데 이번에도 마찬가지 였다.

먼저 시간초과가 발생한 코드를 설명하자면

 

1. N X N테이블에 유사도가 적용된 그래프를 입력한다

2. 0인 부분을 탐색해서 상하좌우로 이동해서

위아래에서 가장 가까운 값 중 최솟값(ud),

좌우에서 가장 가까운 값 중 최솟값(lr)을 찾아낸다.

그 두개의 값 중 가장 작은 값을 0대신 입력하면 되는데 

바로 입력을 해버리면 안되고 잘 저장해두었다가 모든 연산이 종료 된 후 추가해주어야한다.

도중에 추가를 해주면 유사도에 영향을 끼치게 된다.

그래서 temp라는 배열을 만들어 [i,j,값]형태로 저장하게 된다.

그리고 마지막에 temp를 활용하여 graph를 완성시켜준 후 Quest에서 요청하는 값을 리턴해주면 된다.

import sys
from itertools import permutations
#sys.stdin = open("/Users/positive/Desktop/무제 폴더/Algorithm/230105/15591in.txt","r")
input = sys.stdin.readline

N,Q = map(int,input().split())
T = [[0 for _ in range(N+1)]for _ in range(N+1)]
USADO = []
Quest = []
temp=[]
for _ in range(N-1):
  USADO.append(list(map(int,input().split())))
for _ in range(Q):
  Quest.append(list(map(int,input().split())))


for i in USADO:
  T[i[0]][i[1]] = i[2]
  T[i[1]][i[0]] = i[2]



for i in range(1,N+1):
  for j in range(1,N+1):
    if i!=j and T[i][j]==0:
      ud = 0
      lr = 0
      ud_i=1
      lr_i=1
      ud_temp=[]
      lr_temp=[]
      while(True):
        if j+ud_i < N+1 and T[i][j+ud_i]!=0:
          ud_temp.append(T[i][j+ud_i])
        if j-ud_i > 0 and T[i][j-ud_i]!=0:
          ud_temp.append(T[i][j-ud_i])
        if len(ud_temp)==0:
          ud_i+=1
          continue
        elif(len(ud_temp)>0):
          ud = min(ud_temp)
          break

      while(True):
        if i+lr_i < N+1 and T[i+lr_i][j]!=0:
          lr_temp.append(T[i+lr_i][j])
        if i-lr_i > 0 and T[i-lr_i][j]!=0:
          lr_temp.append(T[i-lr_i][j])
        if len(lr_temp)==0:
          lr_i+=1
          continue
        elif(len(lr_temp)>0):
          lr = min(lr_temp)
          break
      temp.append([i,j,min(ud,lr)])
for i in temp:
  T[i[0]][i[1]]=i[2]
  T[i[1]][i[0]]=i[2]

for i in Quest:
  cnt=0
  for j in range(1,N+1):
    if(T[i[1]][j]>=i[0]):
      cnt+=1
  print(cnt)

 수많은 반복문이 사용되어서 시간초과가 날것이다.

정답은 블로그를 통해 확인하였다.

https://steadily-worked.tistory.com/877