BFS (2) 썸네일형 리스트형 [백준] 1389번 : 케빈 베이컨의 6단계 법칙 (Python) 문제 : https://www.acmicpc.net/problem/1389 케빈 베이컨의 6단계 법칙에 의하면 지구에 있는 모든 사람들은 최대 6단계 이내에서 서로 아는 사람으로 연결될 수 있다. 케빈 베이컨 게임은 임의의 두 사람이 최소 몇 단계 만에 이어질 수 있는지 계산하는 게임이다. 이 문제는 가장 작은 케빈 베이컨을 가지는 유저를 찾는 문제다. 플로이드 워셜 알고리즘 사용import sysfrom queue import PriorityQueueinput = sys.stdin.readlineN, M = map(int, input().split()) # 유저의 수 N, 친구 관계의 수 Mrel = [[sys.maxsize for _ in range(N+1)] for _ in range(N+1)] .. [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.. 이전 1 다음