728x90 🥇Baekjoon Solutions/그래프(BFS, DFS, 다익스트라, 플로이드 와샬)10 [C++] 백준 11657번: 타임머신 https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 중요풀이 벨만-포드 알고리즘을 사용하는 대표적인 예제 문제입니다. 노드 사이에 가중치가 음수값을 갖기 때문에 다익스트라 알고리즘이 아닌 벨만-포드 알고리즘을 사용해줍니다. 거리 값이 INF이 아닌 노드들을 체크하여 이동할 수 있는 간선의 가중치를 계산하여 더 작은 값으로 갱신해 줍니다. 여기서 음의 가중치를 갖는 간선이 있다면 그 구간을.. 2021. 8. 27. [C++] 벨만-포드(Bellman - Ford) 알고리즘 벨만-포드 알고리즘이란? 벨만-포드 알고리즘은 가중치 방량 그래프에서 최단 경로 문제를 푸는 알고리즘입니다. 다익스트라 알고리즘에서 간선의 가중치가 음수일 수 없었던 것에 반해 벨만-포드 알고리즘은 가중치를 음수 값으로 갖는 것이 가능합니다. 다만 속도 측면에서 다익스트라 알고리즘이 벨만-포트 알고리즘에 비해 빠른 속도를 갖습니다. 과정은 어떤 한 정점에서 어떤 다른 정점으로 갈 때 그 정점의 개수가 N개면 최대 N-1개의 간선을 사용해야 합니다. 그렇게 시장 정점에서 각 정점까지 가는 가는 최소 가중치합을 간선의 선택개수를 N - 1개까지 증가시키며 비교해주면 됩니다. 그렇게 최소 값들을 유지시키면 됩니다. 마지막으로 N - 1 번째 시행했을 때 남은 값들을 출력합니다. 예시 코드 #include #i.. 2021. 8. 26. [C++] 백준 10159번: 저울 https://www.acmicpc.net/problem/10159 10159번: 저울 첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 www.acmicpc.net 중요풀이 플로이드 와샬 알고리즘을 활용하여 문제풀이를 진행합니다. 서로 비교가 가능한 노드들을 체크하여 최종적으로 전체에서 비교 가능한 노드와 자기자신으로 오는 경우를 빼줍니다. 소스코드 #include #include using namespace std; int INF = 200001;// 노드가 최대 100, 간선의 수가 최대 100,000개 이기 때문에 최소 1000.. 2021. 8. 24. [C++] 백준 11404번: 플로이드 https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 중요풀이 가장 기본적인 플로이드 와샬 알고리즘을 활용한 문제입니다. 소스코드 #include using namespace std; int INF = 10000001;// 노드가 최대 100, 간선의 수가 최대 100,000개 이기 때문에 최소 10000001으로 설정 int node[101][101]; int dp[101][101]; void floydWarshall(int n) { //그래프 초.. 2021. 8. 24. [C++] 플로이드 와샬(Floyd Warshall) 알고리즘 개념 플로이드 와샬 알고리즘이란? 다익스트라 알고리즘이 하나의 정점에서 출발했을 때 다른 모든 정점으로의 최단 경로를 구하는 알고리즘이라면 플로이드 와샬 알고리즘은 모든 정점에서 모든 정점으로의 최단 경로를 구하는 알고리즘입니다. 핵심 아이디어는 거쳐가는 정점을 기준으로 최단 거리를 구하는 것입니다. 예시코드 int node[n + 1][n + 1];//입력받기 int dp[n + 1][n + 1];//다이나믹 프로그래밍 void floydWarshall(int n) { //그래프 초기화 for (int i = 1; i 2021. 8. 24. [C++] 백준 13549번: 숨바꼭질 3 https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 중요풀이 그래프 탐색을 기반으로 너비 우선 탐색 기법을 활용하여 풀이를 진행하였습니다. #include #include using namespace std; bool check[150001]; int time[150001]; void bfs(int start,int end) { queueq; q.push(start); check[start] = true; whil.. 2021. 8. 23. [C++] 백준 11779번: 최소비용 구하기 2 https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 중요풀이 가장 유명한 알고리즘 중 하나인 다익스트라 알고리즘을 기반으로 풀이되는 문제입니다. 큐를 활용하여 풀이를 진행해 주어야 합니다. #include #include #include using namespace std; vector city[1001]; vectorv[1001]; int INF = 100000001;// 전체길이가 1억까지는 가능하기 때문에 그것.. 2021. 8. 23. [C++] 다익스트라(Dijkstra) 알고리즘 개념 다익스트라 알고리즘이란? 다익스트라 알고리즘은 다이나믹 프로그래밍을 활용한 대표적인 최단 경로 탐색 알고리즘입니다. 대표적으로 인공위성 GPS 소프트웨어 등에서 많이 사용됩니다. 다익스트라 알고리즘은 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려줍니다.(음의 간선은 포함 불가) 기본적으로 다익스트라 알고리즘은 하나의 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 그대로 사용한다는 특징이 있습니다. 예시코드 void Dijkstra(int s, int e) { priority_queuepq; // {index, distance} for (int i = 1; i 2021. 8. 23. [C++] DFS(Depth First Search), BFS(Breath First Search) 개념 깊이 우선 탐색(Depth First Search) 루트 노드를 시작으로 다음 분기로 넘어가기 전에 해당 분기를 끝까지 탐색하는 탐색 방법 예시코드 void dfs(int x){ if(check[x]) return;//방문한 곳인지 체크 check[x] = true; for(int i = 0; i < a[x].size(); i++){ int nx = a[x][i]; dfs(nx); } } 장점 - 단지 현 경로상의 노드들만 기억하면 되기 때문에 저장 공간의 수요가 적습니다다. - 목표노드가 깊은 단계에 있는 경우에 빠르게 구할 수 있습니다. 단점 - 해가 없는 경로에 깊이 빠질 가능성이 있습니다. - 얻어진 해가 최단 경로를 통해 얻어진다는 보장이 없습니다. (위의 이미지에서 구해야 하는 해는 2번인.. 2021. 8. 23. 이전 1 2 다음 728x90
