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;..
https://www.acmicpc.net/problem/1504 반드시 거쳐야 하는 두 개의 정점을 a,b라 하면 1->a->b->n 의 최단 경로와 1->b->a->n의 최단 경로의 길이 중 더 작은 것이 답이다. 각각 다익스트라를 3번씩 돌려주면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152#include #include #include #include #define INF 800001using namespace std; int n,m,u,v,w,a,b,p1,p2,ans;vector adj[801]; int dijkstra(int s,int e){ vector dist..
https://www.acmicpc.net/problem/1753 다익스트라 (Dijkstra) 알고리즘은 모든 간선의 가중치가 음수가 아닌 그래프에서 한 정점에서 다른 모든 정점까지의 최단거리를 구하는 알고리즘이다. 가중치가 모두 같다면 BFS로 최단거리를 구할 수 있다. 먼저 시작점으로 부터의 최단거리를 나타내는 dist 배열을 할당하고 INF로 초기화한다. 일단 시작점의 최단거리가 0임은 알 수 있다. 그 다음 우선순위 큐(최소힙)을 이용하여 지금까지 구한 정점까지의 거리 중 최소값을 빼면서 인접 정점들을 검사한다. dist 값이 갱신될 때마다 큐에 (지금까지 찾은 최단거리,정점)을 넣어준다. 이 과정을 반복하다보면 시작점으로부터 다른 모든 정점까지의 최단거리에 해당하는 간선들로 이루어진 스패닝 트..
https://www.acmicpc.net/problem/1463 1로 만드는 최소 연산 횟수는 1에서 N까지 만드는 최소 연산 횟수와 같다. 이를 d[i]이라 하면 이전에 올 수 있는 연산들 중 최소에 1을 더하면 된다. d[i]=min(d(i-1],d[i/3],d[i/2])+1 Top-Down 구현 123456789101112131415161718192021#include #include using namespace std; int n,d[1000001]; int go(int n){ if(n==1 || d[n]) return d[n]; d[n]=go(n-1)+1; if(n%3==0) d[n]=min(d[n],go(n/3)+1); if(n%2==0) d[n]=min(d[n],go(n/2)+1); ret..
https://www.acmicpc.net/problem/1003 f(n)을 호출할 때 f(0)과 f(1)이 각각 호출되는 횟수의 점화식은 d[n]=d[n-1]+d[n-2] 로 같다. 기저값만 1,0과 0,1으로 각각 다르므로 f(1)에 관한 d 배열값이 하나씩 밀려서 나타난다. 따라서 f(0)에 관한 값만 구하고 출력할때 d[n],d[n+1]을 출력해주면 된다. 1234567891011121314151617#include int t,n,d[42]; int main(){ d[0]=1; for(int i=2;i
https://www.acmicpc.net/problem/1431 정렬 기준에 따라 비교 함수를 만들어준다. 1234567891011121314151617181920212223242526272829303132333435#include #include #include #include using namespace std; bool cmp(string &a,string &b){ int s1=a.size(),s2=b.size(); if(s1!=s2) return s1
https://www.acmicpc.net/problem/1305 길이가 N인 광고판이 있고 광고(문자열)가 광고판을 꽉 채우면서 반복되서 나타난다. 이 때 가능한 광고의 길이 중 가장 짧은 것을 찾는 문제이다. 광고가 반복해서 밀려나면서 뒤에서도 나타난다. 따라서 광고판에서 prefix와 suffix가 같을 때 길이의 최대값을 구하고 N에서 이를 빼주면 가장 짧은 광고의 길이이다. 이는 KMP에서 실패 함수의 정의이다. 123456789101112131415161718192021#include #include #include using namespace std; int main(){ int n; string s; cin>>n>>s; vector pi(n); pi[0]=0; for(int i=1,j=0;..