글 읽기 - 16940 python3 시간초과관련 질문드립니다.

bcc0830 4년 전 0

안녕하세요 16940번 풀다가 TC는 다맞고 게시판 반례도 체크했을때는 정답이 나오는데 시간초과가 되어 질문드립니다.

우선 제 코드의 로직은 다음과 같습니다

1. 입력된 마지막 줄이 맞는지 아닌지를 검사해야 하니까 입력된 마지막 줄이 애초에 큐에 들어갈 수 있는지 확인한다.

2. 그러나 각각의 인접 리스트의 길이가 다르고 이미 간 점은 다시 갈 필요가 없으므로 체크를 해주면서 각 정점마다 반복문을 몇번 수행할 것인지 정한다.

3. 현재 정점에서 갈 수 있으며 아직 방문하지 않았다면 입력으로 받은 값을 큐에 저장한다.

4. 입력받은 리스트를 2에서 정한 길이만큼 잘라준다.

5. 현재 정점에서 갈 수 없으면 반복문을 탈출한다.

어떤 부분에서 시간을 줄일 수 있을까요?

고수님들의 고견 부탁드립니다.

감사합니다.

import sys, collections
n = int(sys.stdin.readline())
adj_list = dict().fromkeys([i for i in range(n + 1)]) # 인접 리스트 생성
for i in adj_list:
    adj_list[i] = set()
for i in range(n - 1):
    temp = list(map(int, sys.stdin.readline().split()))
    adj_list[temp[0]].add(temp[1])
    adj_list[temp[1]].add(temp[0])
    # 인접리스트에 대응관계 표시
test_case = list(map(int, sys.stdin.readline().split())) # 마지막 줄로서 맞는지 틀린지 판단해야 함
queue = collections.deque() # 큐 생성
check = [False] * (n + 1) # 정점을 갔는지 안갔는지에 대한 정보를 알려주는 check 배열
ans = True
def bfs_list(list, ans):
    queue = collections.deque()
    queue.append(list[0]) # 맨처음 입력리스트, 즉 test_case의 첫 원소를 넣음
    list = list[1:] # 첫 원소는 무조건 들어가므로 test_case는 두번째 원소부터 사실상 검사해야함
    while queue:
        next = queue.popleft()
        check[next] = True # pop한 정점을 방문 했으니 True로 바꿔줌
        rotate = len(adj_list[next]) # 본문의 2의 '각 정점 당 몇번 방문할지'를 체크해주는 변수 rotate 생성
                                     # 원래의 인접리스트에서 이미 간 정점의 수을 빼준만큼 count
        for i in adj_list[next]:
            if check[i] == True:
                rotate -= 1
        for a in range(rotate):
            if list[a] in adj_list[next] and check[list[a]] == False: # 입력리스트의 원소가 인접리스트에 속하는지, 그리고 
                                                                      # 방문하지 않았는지 체크
                queue.append(list[a]) # 조건에 부합하면 큐에 넣는다
                check[list[a]] = True # 다시 꺼낼 예정이니 입력리스트(test_case)의 원소도 방문했다고 처리한다
            elif list[a] not in adj_list[next]: # 입력리스트에 없는지 체크
                ans = False
                return ans # 바로 False를 리턴시키고 반복문 종료
        list = list[rotate:] # False가 아니라면 test_case, 즉 입력리스트를 해당 정점의 rotate만큼 잘라준다
    return ans

print(bfs_list(test_case, ans))

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

문제

문제

출처

ICPC

16940 python3 시간초과관련 질문드립니다.

bcc0830 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말