알고리즘!/Graph25 [C/C++] 백준 1916: 최소비용 구하기 (다익스트라 구현하기!) https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 이번에 드디어 다익스트라 알고리즘을 배워서 실제 문제 풀이에 적용하였다. 알고리즘 문제해결 전략에 나와있는 것을 응용하여 해결했다. 1. 준비작업 1-1. vector adj_list[100001] 먼저 각 노드들의 인접리스트를 만들 이차원 백터 vector adj_list[100001]을 선언해주었다. 이 백터의 역할은 a번째 노드와 연결되어 있는 b번째 노드까.. 2023. 9. 13. [C/C++] 13549: 숨바꼭질 3 (BFS,Queue) https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 결론부터 말하자면 이 문제는 queue를 이용해 bfs로 풀 수 있는데 이때 2의 배수일 때는 0초만에 도달 가능하다는 것만 유의하면 된다. 구현?? 이를 구현하기 위해서 내가 사용했던 방법은 함수 after_onesec와 after_zero이다. after_onesec는 1초뒤에 갈 수 있는 곳을 queue에 넣는 방식으로 동작되는데 이때 queue.fron.. 2023. 9. 12. [C/C++] 백준 11404: 플로이드 (플로이드-워셜 알고리즘) https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 플로이드-워셜 알고리즘? 알고리즘 제목에서도 알 수 있다싶이 이 문제는 한 도시에서 다른 도시까지 필요한 비용의 최솟값을 구하는 알고리즘 문제이기 때문에 그래프에서 한 지점에서 다른 지점까지의 최솟값을 구하는 알고리즘인 플로이드-워셜 알고리즘을 사용하면 된다. 특징으로는 다익스트라 알고리즘에 비해 구현이 쉽고 삼중 반복문을 사용하기 때문에 O(V^3)의 시간 복잡도를 갖는다. 삼중 반복문을 돌때 .. 2023. 9. 11. [C/C++] 17070: 파이프 옮기기 1 이 문제도 (1,2)를 시작해서 graph를 탐색하며 (n,n)까지 가는 경우의 수를 구하는 문제이기 때문에 그래프 탐색 이론을 사용해야한다. 내가 구현한 방식으로는 현재 지점이 이전 지점에서 어떻게 왔냐 (1.가로 2.대각선 3.세로)에 따라서 탐색의 방향을 정했기 때문에 2차원 배열을 이용하여 queue를 사용한 BFS보다는 DFS가 훨씬 쉽다고 판단하여 DFS를 이용하여 문제를 풀었다. DFS에서 이전 지점에서 어떻게 왔냐에 따라 아래 코드처럼 나누었다. void DFS(int n,int x,int y) { if(previous[y][x]==1) //오른쪽으로 감 GoRight(n,x,y); if(previous[y][x]==2) //대각선으로 감 GoDiagonal(n,x,y); if(previo.. 2023. 8. 29. 이전 1 2 3 4 5 6 7 다음
