7월 29일 토요일 코테: 기말고사 : 계속 시도해봤지만 틀린 문제

 

No. 1

 

 

-  문제 :연결된 그래프 2

https://www.codetree.ai/problems/connected-graph-2?utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

코드1 

문제를 잘못이해함 .. 직접연결이 많은걸 찾는 코드를 짰는데.. 문제에서 요구하는 값은 간접연결된 값도 다포함이었음

n,m= map(int,input().split())

#그래프 
graph ={i+1:[] for i in range(n)}

#간선 세팅
for i in range(m):
    A,B= map(int,input().split())
    graph[A].append(B)

maxlen=0
maxnum=0 
maxnumlist=[] 

for i in range(1,n+1):
    #존재여부 체크 
    if graph[i] and (len(graph[i]) > maxlen):
        maxlen = len(graph[i])
        maxnum = i
        maxnumlist=[i]  #리스트 초기화 하고 i 만 넣기 
    elif len(graph[i]) == maxlen:
        maxnumlist.append(i)

#오름차순으로 정리
maxnumlist.sort()
print(*maxnumlist)

코드2

런타임에러1

n,m= map(int,input().split())

#그래프 
graph ={i+1:[] for i in range(n)}

#간선 세팅
for i in range(m):
    A,B= map(int,input().split())
    graph[A].append(B)


#연속적으로 가서 체크해봐야함 

#실행조건
#종료조건
#재귀호출 조건
def func(idx): # 딕셔너리에서 idx 번째 확인할 차례 
    global leng #해당 정점 연결된 간선 개수
    global graph
    #종료조건
    
    if not graph[idx] : #그래프가 비어있다면 
        return 

    #재귀 호출 부분 
    leng += len(graph[idx])
    for t in graph[idx] :#그래프에서 하나씩 가져와서 체크 
        func(t)


# 그래프 간선확인해서 max 찾기 
maxlen=0
maxnum=0 
maxnumlist=[] 

for j in graph.keys(): 
    leng=0 #키별 개수 초기화 
    func(j)

    #비교
    if leng > maxlen: 
        maxlen = leng
        maxnumlist= [j]
    elif leng == maxlen:
        maxnumlist.append(j)


#maxnumlist.sort()
print(*maxnumlist)
    

'''

for i in range(1,n+1):
    #존재여부 체크 
    if graph[i] and (len(graph[i]) > maxlen):
        maxlen = len(graph[i])
        maxnum = i
        maxnumlist=[i]  #리스트 초기화 하고 i 만 넣기 
    elif len(graph[i]) == maxlen:
        maxnumlist.append(i)

#오름차순으로 정리
maxnumlist.sort()
print(*maxnumlist)
'''

 

시간초과로 생각하고..값을 확인한  간선은 ... 값을 저장하는걸로 다시 짜봄 

계속런타임에러  + 코드 더 이상해짐 

코드3

n,m= map(int,input().split())

#그래프 
graph ={i+1:[] for i in range(n)}

#간선 세팅
for i in range(m):
    A,B= map(int,input().split())
    graph[A].append(B)


#연속적으로 가서 체크해봐야함 

#실행조건
#종료조건
#재귀호출 조건

#호출했을때 이미 연결 간선수를 아는거면.. 걍 그값만 더하는걸로 하기 
shortcut = [-1 for _ in range(n)]

def func(idx): # 딕셔너리에서 idx 번째 확인할 차례 
    global leng #해당 정점 연결된 간선 개수
    global graph
    global shortcut
    
    #종료조건    
    if not graph[idx] : #그래프가 비어있다면   
        return 




    #재귀 호출 부분 
    
    for t in graph[idx] :#그래프에서 하나씩 가져와서 체크 
        if shortcut[t-1] != -1 : # 지름길이 존재한면
            leng += shortcut[idx-1] # 재귀 호출 하지말고 해당값 추가
        else :
            func(t)
            

    #자기자신 과 연결된 애 추가     
    leng += len(graph[idx])

    
    


# 그래프 간선확인해서 max 찾기 
maxlen=0
maxnum=0 
maxnumlist=[] 
key = graph.keys()

for j in key: 
    leng=0 #키별 개수 초기화 
    func(j)
    shortcut[j-1] = (leng-1)
    
    #비교
    if leng > maxlen: 
        maxlen = leng
        maxnumlist= [j]
    elif leng == maxlen:
        maxnumlist.append(j)


#maxnumlist.sort()
print(*maxnumlist)

 

 

새롭게 알게된것 

 

런타임 에러를.. 시간초과라고 생각해버림.ㅜ 

 

주의할점