https://www.acmicpc.net/problem/1854 각 정점의 1번 도시로 부터의 K번째 최단 경로의 소요시간를 찾는 문제이다. 각 정점마다 소요시간들을 저장할 우선순위 큐(Priority Queue)를 할당한다. 그리고 다익스트라를 돌리면서 만약에 해당 정점의 큐의 크기가 K보다 작다면 시간을 그냥 추가해주고 K까지 꽉찼다면 큐의 top(최대값)과 비교하여 새로운 시간이 더 작다면 기존 값을 pop해주고 새로운 값을 넣어주면 된다. 우선순위 큐를 이용하는 이유는 현재까지의 최대 소요시간을 빠르게 찾기 위해서이다. 배열을 사용하면 새로운 거리를 추가하는데 O(1)이 걸리지만 최대값을 찾을 때마다 O(N)이 걸리기 때문에 비효율적이다. 우선 순위 큐를 사용하면 추가하는데 O(logN), 찾는..
https://www.acmicpc.net/problem/2667 지도를 스캔하면서 단지(연결요소)를 찾고 BFS나 DFS를 이용하여 각 단지마다 집의 수를 세준다. 123456789101112131415161718192021222324252627282930313233343536#include #include #include using namespace std; int n,map[25][25],cnt;int dx[4]={0,0,-1,1},dy[4]={-1,1,0,0};vector ans; void dfs(int x,int y){ cnt++; map[x][y]=0; for(int i=0;i
https://www.acmicpc.net/problem/6593 3차원 상에서 시작 지점 S에서 출구 E까지의 최단 거리를 구하는 문제이다. BFS로 구할 수 있다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556#include #include using namespace std; int l,r,c;char map[31][31][31];bool visit[31][31][31];int dx[6]={-1,1,0,0,0,0};int dy[6]={0,0,0,0,-1,1};int dz[6]={0,0,-1,1,0,0};queue q; void bfs(){ int depth=1;..