글 읽기 - (python3,시간초과,dfsbfs x)고수님들 조언 부탁드립니다😟

sglim9607 3년 전 0

코드를 짜고 시간초과가나서 질문들을 쭉 봤더니 대게 bfs dfs로 문제를 풀었더군요.

저는 단순히 리스트 두개에 간선 두점을 따로 따로 저장하고 '리스트 인덱스' 를 이용해 리스트를 서치해 점이 중복되면 하나의 선으로 합쳐주는 방법으로 풀었습니다.

입력방식을 sys를 이용한것으로 바꾸고 break를 추가했습니다. pypy로 해보아도 시간초과가 뜨네요.. dfs가 답일까용..? 괜찮은 아이디어로 짠 것 같아 버리고 싶지 않내요 ㅠ

import sys

n, m = map(int, sys.stdin.readline().split())

m1 = []
m2 = []

count = 1

for i in range(0, m):

    a, b = map(int, sys.stdin.readline().split())

    m1.append(a)
    m2.append(b)


for i in range(0, m):

    point1 = m1[0]
    point2 = m2[0]

    for j in range(1, len(m1)):

        if m1[j] == point1:

            del m1[0], m1[j-1]
            m1.insert(0, m2[j])
            del m2[j]
            break

        elif m2[j] == point1:

            del m1[0], m2[j]
            m1.insert(0, m1[j-1])
            del m1[j]
            break

        elif m1[j] == point2:

            del m2[0], m1[j]
            m2.insert(0, m2[j-1])
            del m2[j]
            break

        elif m2[j] == point2:

            del m2[0], m2[j-1]
            m2.insert(0, m1[j])
            del m1[j]
            break

        elif j == len(m1)-1:
            count = count + 1
            del m1[0], m2[0]
            break

print(count)

dietomorrow 3년 전 0

코드 상 0번 인덱스에 삽입, 0번 인덱스 삭제 등은 O(N)의 시간이 소요됩니다.

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

문제

문제

출처

ICPC

(python3,시간초과,dfsbfs x)고수님들 조언 부탁드립니다😟

sglim9607 3년 전 0

dietomorrow 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말