풀이 플로이드워셜, BFS, 다익스트라 전부가 가능한 문제. - BFS: 예은이의 수색범위를 생각하면서 노드를 방문해야한다. 두 점을 거쳐 지나갈 경우, 합산 필요. - 다익스트라: 한 노드에서 모든 노드까지의 최단거리를 계산하는 알고리즘이기에 for문을 통해서 모든 노드를 다익스트라 알고리즘에 넣어서 돌려야함. - 플로이드워셜: 모든 노드에서 모든 노드까지의 거리를 한번에 구해주는 알고리즘. 저는 플로이드워셜로 문제를 풀어주었습니다. https://sunghyun98.tistory.com/66 [알고리즘] 플로이드 워셜 최단경로 알고리즘이며 모든 노드에서 모든 노드로부터 최단경로를 구할 때 사용하는 알고리즘이다. 플로이드 워셜 vs 다익스트라 저번 시간에 다뤘던 한 지점에서 모든 노드로의 최단경로를 s..

https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 풀이 계획 - 가중치가 다르게 주어진 그래프 이동을 하는 문제 - 한 정점에서 다른 모든 정점으로부터의 최단거리 계산 - 다익스트라 알고리즘 적용 코드 # 13549번 숨바꼭질 3 import sys import heapq input = sys.stdin.readline INF = sys.maxsize def rangeValid(v): if 0 dist: if..

https://www.acmicpc.net/problem/13424 13424번: 비밀 모임 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 방 www.acmicpc.net 풀이 다익스트라 알고리즘을 이용해서 친구들이 이동할 수 있는 방의 최소 거리들을 더해주면 됩니다. # 13424번 비밀 모임 import heapq import sys input = sys.stdin.readline INF = 10**9 def dijkstra(start, graph, distant): dis = distant q = [] heapq.heappush(q, (0, start)) di..

https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 풀이 플로이드 와샬을 이용하여 문제를 풀어주었다. 물론 BFS, DFS를 이용해서 풀어주어도 좋다. # 1389번 케빈 베이컨의 6단계 법칙 import sys INF = sys.maxsize m, n = map(int, input().split()) graph = [[INF]*(m+1) for i in range(m+1)] for _ in rang..

https://www.acmicpc.net/problem/2610 2610번: 회의준비 첫째 중에 회의에 참석하는 사람의 수 N이 주어진다. 참석자들은 1부터 N까지의 자연수로 표현되며 회의에 참석하는 인원은 100 이하이다. 둘째 줄에는 서로 알고 있는 관계의 수 M이 주어진다. 이 www.acmicpc.net 풀이 문제풀이에 BFS와 플로이드와샬 알고리즘을 사용해주었다.BFS => 위원회의 개수를 세는데 사용플로이드 와샬 => 최단경로 계산 BFS는 우리가 BFS 사이클 문제를 많이 풀어왔다면 문제없이 해결 할 수 있었을 것이다.플로이드 와샬 또한 우리가 양방향 그래프이며 노드간의 직접적인 의사전달이 가능하다면 비용 1을 넣어주었다. 문제는 출력문을 뽑아주는것인데 다음단계를 거쳐 출력했다. 1, BF..

https://www.acmicpc.net/problem/11780 11780번: 플로이드 2 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 풀이 이전에 풀어본 플로이드와 다른점은 경로를 출력하는 것이다. 출력을 할 수 있게 visit리스트를 추가했다. # 11780번 플로이드 2 import sys input = sys.stdin.readline INF = sys.maxsize n = int(input()) m = int(input()) # 간선 정보를 저장할 2차원 리스트 graph = [[INF]*(n+1) for _ in r..

https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 풀이 플로이드와셜 알고리즘을 사용한다. 문제에서 출발지와 도착지가 같지만 비용이 다른 노선이 있기에 최소비용 노선을 골라서 2차원 리스트에 넣어주어야한다. # 11404번 플로이드 import sys input = sys.stdin.readline INF = sys.maxsize n = int(input()) m = int(input()) graph = [[INF]*(n+1) for _ in ra..

https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 풀이 다익스트라 알고리즘을 사용해서 풀어주면된다. 추가로 경로를 나타내어야하는데 최단경로가 갱신될 때마다 move리스트에 다음노드의 인덱스에 현재 노드를 저장해주었다. 그런 뒤 리스트에 새로 담아주면된다. # 11779번 최소비용 구하기 2 import sys import heapq INF = sys.maxsize input = sys.stdin.readline #..