글 읽기 - python dfs 시간초과

minjoon1324 3년 전 0

시간초과가 왜 발생하는지 모르겠어요 도저히..

dic를 이용해서 거리가 1000이하인곳을 이어주는 그래프를 만들었습니다.

그 뒤 dfs를 활용했습니다.

부탁드립니다 고수님들!

t = int(input())

for i in range(t):
    n = int(input())
    answer = "sad"
    m=[]
    for i in range(n+2):
        x,y = map(int,input().split())
        m.append([x,y,i])
    dic = {}
    for i in range(len(m)-1):
        for j in range(i+1,len(m)):
            if abs(m[i][0]-m[j][0])+abs(m[i][1]-m[j][1]) <=1000:
                if m[i][2] in dic.keys():
                    dic[m[i][2]].append(m[j][2])
                else:
                    dic[m[i][2]]=[m[j][2]]
                if m[j][2] in dic.keys():
                    dic[m[j][2]].append(m[i][2])
                else:
                    dic[m[j][2]]=[m[i][2]]
    # print(dic)
    visited=[False for i in range(n+2)]


    def dfs(start, end, visited):
        # print("start: ", start)
        global answer
        if start == end:
            answer = "happy"
            return answer

        visited[start] = True
        for i in dic[start]:
            if visited[i] ==False:
                dfs(i, end, visited)
                visited[i] = False
        return answer

    print(dfs(0,n+1,visited))

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

문제

문제

출처

ICPC

python dfs 시간초과

minjoon1324 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말