Problem solving70 [BOJ] 11403. 경로 찾기 (C++) 문제 가중치 없는 방향 그래프가 주어졌을 때, 모든 정점에 대해서, 길이가 양수인 경로가 있는지 없는지 구하기 경로 있으면 1, 없으면 0 출력 생각할 것 모든 정점에 대해 모든 정점으로 간다는 것에서 바로 플로이드 와샬 선택! 코드 #include #include #define INF 1e9 using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int N; // 가중치 없는 방향 그래프가 주어짐, 모든 정점에 대해 모든 정점으로 -> 플로이드 와샬 cin >> N; int input; vector adj(N, vector(N, INF)); for (int i = 0; i < N; i++) { for.. 2023. 7. 25. [BOJ] 14567. 선수과목 (Prerequisite) (C++) 문제 과목의 수 N과 선수 조건의 수 M이 주어진다. 어떤 과목들은 선수과목이 있어 해당되는 모든 과목을 먼저 이수해야만 해당 과목을 이수할 수 있게 되어 있다. 한 학기에 들을 수 있는 과목 수에 제한이 없다 모든 과목은 매 학기 항상 개설된다 모든 과목에 대해 각 과목을 이수하려면 최소 몇 학기가 걸리는지 출력 생각할 것 위상 정렬을 이용하자 연결된 과목에 1을 더해 과목 이수에 소요되는 값을 추가하자 코드 #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int N, M, A, B; cin >> N >> M; vector adj(N + 1); .. 2023. 7. 24. 위상 정렬 (Topology Sort) 그래프에 다양한 조건들이 얽혀있을 때, 조건에 부합하는 일직선의 경로를 찾는 알고리즘 특징 방향 그래프 여러개의 경로가 존재할 수 있음 사이클이 존재하지 않음 알고리즘 구조 진입 차수가 0인 정점을 모두 큐에 삽입하기 큐에서 정점을 꺼냄 꺼낸 순서가 위상정렬된 순서 꺼낸 정점과 연결된 간선의 진입 차수를 1씩 빼기 이후 다시 진입차수가 0이 된 정점을 큐에 삽입 만약, V번 반복하기 전에 큐가 비어있다면 사이클이 발생한 것임 // 인접 행렬과 진입 차수 초기화 vector adj(N + 1); vector inDegree(N + 1); for (int i = 0; i > A >> B; adj[A].push_back(B); inDegree[B]++; } // 진입 차수가 0인.. 2023. 7. 24. [BOJ] 18352. 특정 거리의 도시 찾기 (C++) 문제 어떤 나라에는 1번부터 N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다 X로부터 출발하여 도달할 수 있는 도시 중, 최단 거리가 K인 도시의 번호 출력, 없으면 -1 출력 생각할 것 모든 도로의 거리가 1이므로 가중치가 모두 동일하다! 따라서 BFS를 사용하면 된다 코드 1. BFS BFS는 그냥 큐를 이용한다! 한번씩만 업데이트하므로 visited대신 dist가 INF인지 확인하면 된다. #include #include #include #define INF 1e9 using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int N, M, K, X, A, B; cin >.. 2023. 7. 22. 이전 1 ··· 6 7 8 9 10 11 12 ··· 18 다음