본문 바로가기

알고리즘74

백준 1504번 : 특정한 최단 경로 문제 링크 : www.acmicpc.net/problem/1504 내 풀이(2021.1.25.) : 다익스트라 #include #include #include #include using namespace std; #define MAX_V 800 // 노드 개수의 최대값 int V, E, start_v; // V : 노드의 개수, E : 간선의 개수, start_v : 시작 노드 vector VE_info[MAX_V + 1]; // V개의 노드들에 대한 쌍 (second = 특정 노드로부터 first번 노드까지의 간선값) vector shortest_distance(MAX_V + 1, INT_MAX); // 시작 노드로부터 V개의 도착 노드들까지의 최단 거리 void dijkstra(int start_v).. 2021. 1. 25.
백준 1753번 : 최단경로 문제 링크 : www.acmicpc.net/problem/1753 내 풀이(2021.1.25.) : 다익스트라 #include #include #include #include using namespace std; #define MAX_V 20000 // 노드 개수의 최대값 int V, E, start_v; // V : 노드의 개수, E : 간선의 개수, start_v : 시작 노드 vector VE_info[MAX_V + 1]; // V개의 노드들에 대한 쌍 (second = 특정 노드로부터 first번 노드까지의 간선값) vector shortest_distance(MAX_V + 1, INT_MAX); // 시작 노드로부터 V개의 도착 노드들까지의 최단 거리 void dijkstra(int start_.. 2021. 1. 25.
백준 7569번 : 토마토 문제 링크 : www.acmicpc.net/problem/7569 내 풀이(2021.1.25.) : BFS #include #include #include using namespace std; int N, M, H; int map[100][100][100]; // [z][y][x] = [H][N][M] int dz[6] = {1,-1,0,0,0,0}; int dy[6] = {0,0,-1,1,0,0}; int dx[6] = {0,0,0,0,-1,1}; queue q; bool check() { for (int i = 0; i < H; i++) { for (int j = 0; j < N; j++) { for (int k = 0; k < M; k++) { if (map[i][j][k] == 0) return .. 2021. 1. 25.
최단 경로 개념 코딩 테스트에는 주로 '다익스트라'와 '플로이드 워셜'이 출제 된다. 둘다 방향이 있는 그래프이다. 주로 최단 경로 전체를 출력하는 문제보다는 단순히 최단 거리만을 출력하는 문제가 많다. 아래 설명에서 시간복잡도의 N는 노드의 개수, E는 간선의 개수를 나타낸다. 다익스트라 - 특정 노드에서 모든 노드까지의 최단 거리들을 구함 - 최단 거리 저장 자료 구조 : 특정 노드에 대한 리스트 사용 (1차원 벡터) - 시간 복잡도 : 리스트를 순회하는 알고리즘 = O(N^2) / 힙을 이용한 알고리즘 = O(ElogN) - 음의 간선이 없을 때 사용 가능 플로이드 워셜 - 모든 노드에서 모든 노드까지의 최단 거리들을 구함 - 최단 거리 저장 자료 구조 : 모든 노드에 대한 리스트 사용 (2차원 벡터) - 시간 복.. 2021. 1. 24.

티스토리툴바