글 읽기 - 구현 도움 부탁드립니다.

jsch678 1년 전 0

가능한 경로들을 모두 저장해서, 그 경로상의 페이들을 더해주는 것을 구현하려고 합니다.

편의를 위해서 입력을 받을때, 날짜상 불가능 한 일들은 벌 수 있는 돈을 0으로 취급하였습니다.

" dfs2 " 함수에서 이동 가능한 경로를 저장하고, 그 경로상의 페이들을 더해주고 싶은데 어떻게 구현할 수 있을까요?

'''
그래프를 먼저 만들자. 연결된 노드들의 그래프를 만드는데,
이때 후반기에 날짜가 지나는 것들은 제외한다.

'''
n = int(input())
graph = [[]]
visited = [False] * (100)
for i in range(1,n+1):
    graph.append([])
    a,b = map(int,input().split())
    if (a+i) > (n+1):
        b = 0
    graph[i].append((a,b))
print('graph')
print(graph)

# for i in range(1,n+1):
#     finishday = i + graph[i][0][0]
#     if finishday > n:
#         graph[i][0][1] = 0
cost = 0
def dfs(graph,visited,v):
    if v>n :
        # print(" exceed n ")
        return False
    visited[v]=True #방문처리
    i = (v + graph[v][0][0]) # i의 범위가 선택 가능해야함 꼭 지정된것은 아님. 리스트로 바꿔보자.
    #현재 i는 출발점을 의미함. 가능한 출발점부터 끝 지점까지 선택 가능하게 만들기.
    #그리고 개별 cost를 갖고 재귀함수가 되어야함.
    finish_point = n
    start_list = []
    for j in range(i,n+1):
        start_list.append(j)
    print(" v : ",v)
    global cost
    cost += graph[v][0][1]

    for i in start_list:
        # print( " i list : ", i )
        if not visited[i]: #방문하지 않은 곳이라면
            # visited[i] = True #방문처리
            print("next i : ",i)
            print(" cost : ",cost)

            dfs(graph,visited,i) 
            #여기서 추가할 것은 연결된 노드를 찾는 기능, 
            # 간선의 cost를 구하는 기능, 
            # 후반기에 초과 근무 하는것을 제외하는 기능
    
    return cost
ways = [ ]
def dfs2(graph,visited,v):
    # 가능한 루트를 기억해서 나중에 각각의 cost를 더하는 함수
    if v>n :
        return False
    visited[v]=True 
    i = (v + graph[v][0][0]) 
    start_list = []
    for j in range(i,n+1):
        start_list.append(j)
    print(" v : ",v)

    for i in start_list:
        # print( " i list : ", i )
        if not visited[i]: #방문하지 않은 곳이라면
            visited[i] = True #방문처리
            print("next i : ",i)
            print(" cost : ",cost)

            dfs(graph,visited,i) 
            #여기서 추가할 것은 연결된 노드를 찾는 기능, 
            # 간선의 cost를 구하는 기능, 
            # 후반기에 초과 근무 하는것을 제외하는 기능
    
    return cost        
cost_hap = []
for i in range(1,n+1):
   cost_hap.append(dfs(graph,visited,i))
   cost = 0 
print(max(cost_hap))

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

문제

문제

출처

ICPC

구현 도움 부탁드립니다.

jsch678 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말