728x90 Dijkstra5 백준 No.1261 [알고스팟] BOJ No.1261 [알고스팟] 문제 1261번: 알고스팟 (acmicpc.net) 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 설명 * Dijkstra (다익스트라) * 너비 우선 탐색 (BFS) 주어진 미로의 각 좌표들을 노드라고 생각하고, 좌표에서 이동할 수 있는 방향은 상하좌우로 인접한 네 방향이므로 이 네 방향을 하나의 간선이라고 생각할 수 있다. 좌표의 최대 크기는 100 * 100 이다. 따라서 노드의 최대 개수는 10,000 개가 되며 한 노드당 좌표의 모서리에 위치한.. 2021. 8. 17. 백준 No.11779 [최소비용 구하기2] BOJ No.11779 [최소비용 구하기2] Problem 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 #inc.. 2021. 2. 19. 백준 No.13549 [숨바꼭질3] Baekjoon Online Judge No.13549 [숨바꼭질3] Problem 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 #include #include #include #define pos first #define ti.. 2021. 2. 16. 백준 No.1504 [특정한 최단 경로] Baekjoon Online Judge No.1504 [특정한 최단 경로] Problem 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 .. 2021. 2. 9. Dijkstra (다익스트라) Dijkstra What is Dijkstra? 그래프의 한 노드에서 다른 노드로 갈 때 드는 가중치들의 합의 최소값을 구하는 알고리즘이다. 이 '가중치'를 문제가 요구하는 바에 따라 거리, 비용 등의 형태로 문제에 다양하게 적용시킬 수 있을 것 같다. Explanation A정점부터 탐색을 시작해봤다. 실제 코드에서 알고리즘을 사용할 땐 처음에 시작하고자 하는 정점을 정해주면 된다. 좌측의 표에서 빨간색은 확정된 최소 비용을 나타낸다. A에서 A로 갈 때에는 당연히 비용이 0이므로 확정이다. 숫자 앞에 A를 붙인 이유는 직전에 A에서 왔다는 의미이다. B, C, D E 열에 차례대로 비용을 적어준다. F열은 A에서 F로 가는 간선이 없으므로 inf 라고 하자. 저렇게 나열해준 뒤 확정이 된 빨간색 칸을.. 2021. 2. 8. 이전 1 다음 728x90
