https://www.acmicpc.net/problem/4386 [접근]선을 하나 이을 때마다 두 별 사이의 거리만큼의 비용이 든다고 할 때, 별자리를 만드는 최소 비용을 구하시오. 모든 노드를 돌면서 연결될때의 거리를 edges백터에 저장하고 정렬한다. -> 그 후 유니온 파인드 알고리즘을 활용하여 최소비용을 구한다. [코드]#include #include #include #include #include #include using namespace std;vector> v;int parent[101];vector>> edges;double result=0.0;int find(int x){ if(parent[x]==x) return x; else return parent[x] = fi..
알고리즘
https://www.acmicpc.net/problem/20010 [접근]첫 번째 줄에는 모든 마을을 연결하는 최소 비용을 출력한다. 두 번째 줄에는 마을과 마을을 이동하는 비용이 가장 큰 경로의 비용을 출력한다. 입력받은 서로 다른 두 마을의 번호 a, b (a ≠ b)와 두 마을을 연결하는 비용 c을 비용기준으로 오름차순 정렬하고, 유니온파인드 알고리즘을 활용하여 모든 마을이 연결되도록 하였다. 연결되는 과정에서 루트를 line백터에 저장해두고 추후 반복문을 통해 구역을 돌며 최대값을 저장해 출력한다. [코드]#include #include #include #include using namespace std;vector>> v;vector> line[1001];int n,k,cost =0,m..
https://www.acmicpc.net/problem/1948 [접근]첫째 줄에는 이들이 만나는 시간을, 둘째 줄에는 1분도 쉬지 않고 달려야 하는 도로의 수가 몇 개인지 출력하여라. 시간은 기존 위상정렬 알고리즘을 사용해서 구했고, 도로의 개수는 역방향 DFS 사용해서 구했다. 최장거리의 경로임을 확인하기 위해 dp[now] - w == dp[next] 조건 통해 검증했다. [코드]#include #include #include #include using namespace std;vector> v[100001],rev[100001];vector ind;int n,m,s,d,cnt=0;int dp[100001];bool visit[10001];void revdfs(){ queue q; ..
https://www.acmicpc.net/problem/1005 [접근]위상 정렬 알고리즘을 사용하였고, 동시에 건설되는 시간값은 dp배열에 업데이트해가며 접근했다. [코드]#include #include #include #include using namespace std;vector v[1001];int d[1001], ind[1001], dp[1001];int n, k, w;void solve() { queue q; for (int i = 1; i > t; while (t--) { cin >> n >> k; memset(d, 0, sizeof(d)); memset(ind, 0, sizeof(ind)); memset(dp..
https://www.acmicpc.net/problem/3665 [접근]? : 한노드에서 진입차수를 --했을때 진입차수가 0인 노드가 2개 이상일시 순서가 불확실해진다 -> 큐에 있는 노드의 개수가 2개 이상일 경우 ?를 출력하도록 했다. impossible : 사이클이 존재하는 경우 -> n과 result의 사이즈가 동일하지 않을경우에 impossible을 출력하도록 했다. [코드]#include #include #include #include #include using namespace std;int n,m;vector r;vector map[501];void solve(){ queue q; vector result; bool findthing = false; ..
https://www.acmicpc.net/problem/2252 [접근] 위상 정렬은 1. 사이클이 없고2. 방향 그래프이며3. 순서가 있을 때 사용하는 알고리즘이다. 이 문제는 위상정렬 알고리즘을 사용하여 풀이를 진행하였다. 입력받을 때, 들어오는 노드에 대한 값을 vector v에 저장해두고자신에게 들어오는 노드가 0일 경우, 큐에 push한다. [코드]#include #include #include using namespace std;vector v,result;vector map[100001];int n,m;void solve(){ queue q; for(int i=1;i>n>>m; v.assign(n + 1, 0); result.assign(n +..
https://www.acmicpc.net/problem/3109 [접근]DFS를 사용하였고, 같은 곳을 두번 지날 수 없으므로 방문 체크 후 false하는 과정은 없이 진행하였다. [코드]#include using namespace std;int r,c,count=0;char map[10001][501];int dx[3] = {1,1,1};int dy[3] = {-1, 0, 1};bool check;void solve(int y,int x){ if(x == c-1){ check = true; count++; return; } map[y][x]='x'; for(int i=0;i=c || tmpy=r || map[tmpy][tmpx..
https://www.acmicpc.net/problem/1202 [접근]보석의 무게 기준으로 오름차순, 상덕이의 가방을 오름차순으로 정렬한 후 ,가방의 무게가 낮은 가방부터 돌면서 가방에 넣을 수 있는 보석을 pq에 모두 넣는다. 그 후 pq에서 값을 하나씩 빼며 sum에 더해간다.-> pq는 기본적으로 내림차순 정렬이 되므로 맨 위에 있는 값이 큰 값이 된다. [코드]#include #include #include #include using namespace std;int n,k; vector m; vector> v; priority_queue pq;long long sum =0;void solve(){ int idx=0; for(int i=0;i=v[idx].first){..
https://www.acmicpc.net/problem/9328 [접근 방식]이 문제는 지금은 문을 열지 못하지만 나중에 열쇠를 획득하게 될수도 있다는 중요한 사실이 있었다. 처음에는 dfs로 접근해보았는데 시간초과가 떴었다. -> 열 수 없는 문 위치를 기억하는 Queue와 BFS를 진행할 Queue를 사용해 문제를 해결한다.=> 가장자리에서 모두 접근가능하기 때문에 입력받는 지도를 둘러싸는 칸이 하나 더 있다고 생각하여 문제를 해결한다. [코드]#include #include #include using namespace std;int h,w,maxnum;bool key[26]; bool visit[102][102];char v[102][102];int dy[4] = {1,0,-1,0};int ..
https://www.acmicpc.net/problem/1987 [코드]#include #include using namespace std;int r,c,maxnum= -1;char word[21][21];bool visit[21];int dx[4] = {1,0,-1,0};int dy[4] = {0,-1,0,1};void solve(int x,int y, int count){ maxnum = max(maxnum,count); for(int i=0;i=r || ny=c) continue; if(visit[word[nx][ny]-'A']) continue; check = true; visit[word[nx][ny]-'A']=true; ..
