Loading [MathJax]/jax/output/CommonHTML/jax.js
본문 바로가기
728x90

플로이드–워셜

 2
[백준] 11403번 경로 찾기 [Python] - DFS, BFS, 플로이드–워셜 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i,j)에 대해서, i에서 j로 가는 길이가 양수인 경로가 있는지 없는지 구하는 문제 플로이드–워셜, dfs, bfs를 사용한 코드들을 작성해봤습니다. 더보기 문제 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i,j)에 대해서, i에서 j로 가는 길이가 양수인 경로가 있는지 없는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정점의 개수 N (1≤N≤100)이 주어진다. 둘째 줄부터 N개 줄에는 그래프의 인접 행렬이 주어진다. i번째 줄의 j번째 숫자가 1인 경우에는 i에서 j로 가는 간선이 존재한다는 뜻이고, 0인 경우는 없다는 뜻이다. i번째 줄의 i번째 숫자는 항상 0이다. 출력 총 N개의 줄에 걸쳐서 문제..
[백준] 1389번 케빈 베이컨의 6단계 법칙 [Python] - 플로이드–워셜 유저 N과 그 사이의 그 사이의 친구 관계 수 M이 주어질 때, 모든 사람과의 연결 관계 수의 합이 가장 작은 사람 출력 더보기 문제 케빈 베이컨의 6단계 법칙에 의하면 지구에 있는 모든 사람들은 최대 6단계 이내에서 서로 아는 사람으로 연결될 수 있다. 케빈 베이컨 게임은 임의의 두 사람이 최소 몇 단계 만에 이어질 수 있는지 계산하는 게임이다. 예를 들면, 전혀 상관없을 것 같은 인하대학교의 이강호와 서강대학교의 민세희는 몇 단계만에 이어질 수 있을까? 천민호는 이강호와 같은 학교에 다니는 사이이다. 천민호와 최백준은 Baekjoon Online Judge를 통해 알게 되었다. 최백준과 김선영은 같이 Startlink를 창업했다. 김선영과 김도현은 같은 학교 동아리 소속이다. 김도현과 민세희는 같은 ..

티스토리툴바