BFS (5) 썸네일형 리스트형 [백준] 촌수계산(python) 백준, 촌수계산 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net TL;DR 너비 우선 탐색(BFS) 최단경로찾기 - 다익스트라 알고리즘(Dijkstra algorithm) 문제 요약 1. 여러 사람들에 대한 부모 자식들 간의 관계가 주어졌을 때, 주어진 두 사람의 촌수를 계산하는 프로그램을 작성하라. 2. 두 사람이 친척 관계가 없는 경우는 -1을 출력해야 한다. - 각 사람들이 노드, 노드 간의 길이는 1인 그래프의 형태를 생각할 수 있다. - 주어진 두 사람(노드) 간의 거리를 계산하는.. [백준] 연결 요소의 개수(python) 백준, 연결 요소의 개수 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net TL;DR 깊이 우선 탐색(DFS) 너비 우선 탐색(BFS) 문제 요약 1. 방향 없는 그래프가 주어졌을 때, 연결 요소의 개수를 구하는 프로그램을 작성하시오. - 모든 노드 사이의 움직일 수 있는 무향, 양방향 그래프가 주어질 때, 연결 요소의 개수를 구하는 프로그렘을 작성해야 한다. (연결 요소에 대해서는 입출력 형태에서 확인한다.) 입출력 형태 주어진 그래프를 그림으로 표.. [백준] 그대, 그머가 되어(python) 백준, 그대, 그머가 되어 TL;DR 너비 우선 탐색(BFS) 다익스트라 알고리즘(Dijkstra Algorithm) 문제 요약 1. 바꿀 수 있는 문자 간의 관계가 표현되어 있는 그래프에서 주어진 문자를 바꿀 수 있는 최소 횟수를 반환하라. 2. 문자를 바꿀 수 없는 경우에는 -1을 출력한다. - 문자를 다른 문자로 바꿀 수 있는 관계가 주어진다. - 이 관계들에서 바꾸기를 원하는 문자를 바꿀 문자로 바꾸는데 걸리는 과정의 최소 횟수를 반환하는 프로그램을 작성하면 된다. - 각 문자들을 노드로, 바꿀 수 있는 노드들 사이의 관계를 간선의 형태로 그래프로 표현할 수 있다. 이 때, 그래프는 방향성이 없는 무향 그래프이다. - 노드 사이의 관계를 표현할 때 꺽쇠''가 아닌 괄호'()'를 사용하여 표현한 것.. [리트코드] Network Delay Time(python) 리트코드, Network Delay Time_네트워크 지연 시간 TL;DR 너비 우선 탐색(BFS) 다익스트라 알고리즘(Dijkstra Algorithm) 문제 요약 1. 1부터 n까지 노드가 있는 네트워크가 주어진다. 주어진 네트워크는 출발 노드, 도착 노드, 출발 노드로부터 도착 노드까지 걸리는 시간을 의미한다. 2. 주어진 k 노드로부터 신호를 전달한다고 했을 때 모든 n개의 노드들 도는데 걸리는 시간을 반환하라. 3. 만약 모든 노드를 순회할 수 없다면 -1을 반환하라. - 주어진 k 노드로부터 그래프에 존재하는 모든 노드를 순회할 때의 시간을 반환하면 된다. 이는 가장 k 노드로부터 가장 먼 거리의 노드까지 걸리는 시간을 반환하면 된다. - 모든 노드를 순회할 수 있다면 BFS에서 조회할 수 있.. [백준] DFS와 BFS(python) 백준, DFS와 BFS TL;DR 깊이 우선 탐색(DFS) 너비 우선 탐색(BFS) 문제 분석 1. 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 2. 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고 3. 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 4. 정점 번호는 1번부터 N번까지이다. - 입력으로 주어진 그래프를 DFS와 BFS로 각각 순회한 결과를 출력하는 프로그램을 작성하는 문제이다. - 2번의 조건에 유의하여 문제를 풀어야 한다. 입출력 형태 - 가장 첫 번째 줄에 정점(vertex, node)의 개수와 간선(edge)의 개수, 그리고 시작 정점의 번호가 주어진다. - 두 번째 줄부터는 각 정점 간의 연결관계를 나.. 이전 1 다음
