DFS (5) 썸네일형 리스트형 [Python, 파이썬] SWEA 1249. [S/W 문제해결 응용] 4일차 - 보급로 출발지(S) 에서 도착지(G)까지 가기 위한 경로 중에 복구 시간이 가장 짧은 경로에 대한 총 복구 시간을 구하는 문제. 1. DFSdef DFS(i, j, costs): global min_costs if not (0 메모이제이션+완전 탐색을 위해 풀 수 있는 문제다.상하좌우를 봐서 N x N 범위 안에 점점 이동하는데, 이때 현재 탐색 중인 경로가 현재 구한 경로보다 비쌀 시 DFS를 종료한다. 또, 현재 위치에 이전에 더 저렴한 경로를 찾았을 시 그 경로를 update한다. if cost_map[i][j] 그러나 DFS를 사용하면 한쪽길로 쭉 가기 때문에 시간이 많이 걸린다.그래서 Recurison 오류와, 시간초과가 발생할 가능성이 높다. 2. BFSfrom collec.. [Python, 파이썬] SWEA 2814. 최장 경로 N개의 정점과 M개의 간선으로 구성된 가중치가 없는 무방향 그래프에서의 최장 경로의 길이를 계산하는 문제. def DFS(i, now): global all_max if(now > all_max): all_max = now for child in graph[i]: if not depth[child]: # 방문하지 않았을 시 depth[child] = True DFS(child, now+1) # 자식 노드로 이동 depth[child] = False # 백트래킹 T = int(input()) # 테스트케이스 수 Tfor test_case in range(1, T+1): N, M.. [Python, 파이썬] SWEA 1861. 정사각형 방 어떤 수가 적힌 방에서 있어야 가장 많은 개수의 방을 이동할 수 있는지 구하는 프로그램 당신이 어떤 방에 있다면, 상하좌우에 있는 다른 방으로 이동할 수 있다.물론 이동하려는 방이 존재해야 하고, 이동하려는 방에 적힌 숫자가 현재 방에 적힌 숫자보다 정확히 1 더 커야 한다. 이동할 수 있는 방의 수가 가장 많은 방의 번호는? def Get(): A = [[0 for i in range(N+2)]] # 수열 A # 수열 입력받기 for i in range(N): A.append([0]+list(map(int, input().split()))+[0]) A.append([0 for i in range(N+2)]) return Adef Graph(A): .. [Python, 파이썬] SWEA 2817. 부분 수열의 합 A1, A2, ... , AN의 N개의 자연수가 주어졌을 때, 최소 1개 이상의 수를 선택하여 그 합이 K가 되는 경우의 수를 구하는 프로그램 def DFS(i, current_value): global answer # 합이 K개가 되는 경우의 수 if(current_value > K): # 합이 K를 넘었을 시 return if(current_value == K): # 합이 K일 시 answer += 1 return if(i==N): # 수열 전체 검사 완료 시 return DFS(i+1, current_value) # 현재 자연수 미선택 DFS(i+1, current_value+A[i]) # 현재 자연수 선택T.. [Python, 파이썬] SWEA 5215. 햄버거 다이어트 햄버거 재료에 대한 점수와 가게에서 제공하는 재료에 대한 칼로리가 주어졌을 때, 정해진 칼로리 이하 조합 중에서 점수가 가장 높은 햄버거를 가하는 문제. def BFS(i, taste, hambegur): global max_score # 최대 칼로리 if(hambegur > L): # 최대 칼로리를 넘으면 return if taste > max_score: # 점수가 더 높은 맛 찾았을 시 max_score = taste if(i==N): # 재료 모두 사용 return BFS(i+1, taste+score[i], hambegur+calorie[i]) # 현재 재료 선택 BFS(i+1, taste, hambegur) # 현재 재료.. 이전 1 다음
